Формулы алгебры логики. Вычисление их значений.

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трёх высказываний x,y,z можно построить высказывания

(xÙy)Ú и x .

Первое из них есть дизъюнкция конъюнкции x,y и отрицания высказывания z, а второе высказывание есть импликация, посылкой которой является высказывание x, а заключением – отрицание дизъюнкции высказывания y и конъюнкции высказываний x,z.

Всякое сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции, называется ФОРМУЛОЙ АЛГЕБРЫ ЛОГИКИ.

Формулы алгебры логики будем обозначать большими буквами латинского алфавита A, B, C,…,X, Y,Z,…

Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются.

В связи с этим приведенные выше формулы (xÙy)Ú и x могут быть написаны так: и x , а также xyÚ и x .

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в неё элементарных высказываний. Например, логическим значением формулы в случае, если x=1, y=1, z=0 будет истина, т.е. =1.

Как и в случае с логическими операциями все возможные логические значения формулы, в зависимости от значений входящих в неё элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности.

Например, для формулы таблица истинности имеет вид:

 

Легко видеть, что если формула содержит n элементарных высказываний, то она принимает 2ⁿ значений, состоящих из нулей и единиц, или, что то же, таблица содержит 2ⁿ строк.

 

Задания:

Составить таблицу истинности:

1.	2.	3.
4.	5.	6.
7.	8.	9.