СтудЗона - огромная база рефератов, курсовых и шпаргалок на все случаи жизни!

 
 


Бот знакомств в telegram
@youlove_bot

Применение алгебры высказываний в информатике

Предмет: Информатика
Оцените материал
(0 голосов)
просмотреть полностью

КУРСОВАЯ РАБОТА

по дисциплине «Информатика»

на тему «Применение алгебры высказываний в информатике»

Уфа — 2009

Оглавление стр.

1. Введение.........................................................................

2. Теоретическая часть...........................................................

3. Практическая часть............................................................

4. Список использованной литературы.......................................

Введение

3. Элементы алгебры высказываний. Примеры использования алгебры высказываний в информатике.

Алгебра — это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры — натуральные числа, а операции — сложение и умножение, то это алгебра натуральных чисел. Действия с направленными отрезками (векторами) изучает векторная алгебра.

АЛГЕБРА ВЫСКАЗЫВАНИЙ является составной частью математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы.

Объектами этой алгебры являются высказывания.

Высказывание — это истинное или ложное повествовательное предложение.

Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием.

Предложение <Луна — спутник Земли> есть простое высказывание, предложение <Не сорить!> не является высказыванием.

Высказывания обозначаются большими буквами латинского алфавита.

Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

В алгебре высказываний над ее объектами (высказываниями) определены действия (операции)

Операция логического умножения <И> (конъюнция), или логическое произведение может быть определена с помощью следующей таблицы:

А

В

АВ

1

1

1

1

0

0

0

1

0

0

0

0

Операция логического сложения <ИЛИ> (дизъюнкция) для двух аргументов представдена в виде таблицы

А

В

А+В

1

1

1

1

0

1

0

1

1

0

0

0

Операция логического отрицания <НЕ> осуществляется над одним высказыванием. Истинность высказывания с операцией НЕ определяется таблицей:

A

^A

1

0

0

1

Тождественные высказывания.

Пользуясь определенными выше операциями, можно из простых высказываний образовывать сложные.

Пример: Таблица истинности логической функции

A

B

C

F

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

F = (^A)*(^B)*C + A*(^B)*(^C) + A*B*C = (^A)*(^B)*C + A*((^B)*(^C)+B*C)

Если в таблице истинности одни единицы либо только нули. Это означает, что высказывание либо всегда истинно, либо ложно, независимо от истинности входящих в него высказываний

Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными

Эквивалентные высказывания.

Операции алгебры высказываний обладают следующими важными свойствами:

Логическое умножение:

Логическое сложение:

A·B = B·A

A + B = B + A

(AB)C = A(BC)

(A + B)+ C = A + (B + C)

A·A = A

A + A = A

A·1 = A

A + 1 = 1

A·0 = 0

A + 0 = A

A(B + C) = AB + AC

A + BC = (A + B)(A + C)A + BC = (A + B)(A + C)

Правилa Де-Моргана

^ (A * B) = ^ A + ^ B

^ (A + B) = (^ A) * (^ B)

A

B

НЕ(A+B)

0

0

1

0

1

0

1

0

0

1

1

0

A

B

НЕ(AB)

0

0

1

0

1

1

1

0

1

1

1

0

В алгебре высказываний, как и в другой алгебре, возможны тождественные преобразования.

Вводятся дополнительные операции, такие как эквивалентность (<тогда и только тогда, когда>), импликация (<следовательно>), сложение по модулю два (<исключающее или>), штрих Шеффера, стрелка Пирса и другие.

Эквиваленция — это функция тождества. Она обозначается символами = , ~ , или <=>. Выбираем обозначение А = В. (<тогда и только тогда>). Запись А = В читается как <А эквивалентно В>.

Импликация — это логическое следование. Импликация двух высказываний А и В соответствует союзу <ЕСЛИ:ТО>. Она обозначается символом . Читается как <из А следует В>. Обозначение: A→B.

Логика высказываний послужила основным математическим инструментом при создании компьютеров.