1.Алгебра высказываний

Алгебра логики (алг.выск-й) – раздел мат.логики, в к-м изучаются лог.операции над выск-ями. Объектами алгебры высказываний являются высказывания. Высказывание – это истинное или ложное повествовательное предложение. Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием. Высказывания обозначаются большими буквами латинского алфавита. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

Высказывания строятся над мн-м {B,-(отрицание),^,\/,0,1}, где В –непустое мн-во, над элементами к-го определены 3 операции:

- - отрицание (унарная операция);

^ - конъюнкция (бинарная);

\/ - дизъюнкция (бинарная), а также константы – 0 (л) и лог. 1 (и).

2.Приложения алгебры высказываний

Одним из применений алгебры высказываний является использование ее для анализа сложных, а подчас противоречивых текстов. Алгебра высказываний позволяет научиться моделировать простейшие мыслительные процессы. Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция приобретает смысл вычитания из единицы; — немодульного сложения; & — умножения; — равенства; — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); — непревосходства суммы над 1 (то есть A B = (A + B) <= 1).

3.Формулы. Вывод формул

Выражение (X/\У) —> Z также можно считать формулой — формулой схемы конструирования составных высказываний из более простых.

Понятие формулы алгебры высказываний. В формулу (X/\У) —> Z вместо переменных X, Y, Z можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Q, R, S, X, Y, Z или такими же буквами с индексами Р1 Р2 ..., Q1 Q2, ..., Х1 Х2.

Теперь дадим точное определение формулы алгебры высказываний. Определение 2.1

1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.

2. Если F1 и F2 — формулы алгебры высказываний, то выражения –F1, (F1/\ F2), (F1 v F2), (F1 -> F2), (F1 эквивалентность F2) также являются формулами алгебры высказываний.

3. Никаких других формул алгебры высказываний, кроме получающихся согласно п. 1 и 2, нет.

Формулы А и В называются эквивалентными (обозначается А ~ В), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В.

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение И.

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение Л.

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение И при всех наборах значений переменных.

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение л при всех наборах значений переменных.