Тема.3.Логические операции над высказываниями

▪ Отрицание.

▪ Дизъюнкция.

▪ Конъюнкция.

▪ Импликация.

▪ Эквиваленция.

▪ Понятие бинарной и унарной операции.

Отрицание. Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.

Отрицанеи высказывания х обозначается и читается «не х» или «неверно, что х».

Логические значения высказывания можно описать с помощью таблицы

х

Таблицы такого вида принято называть таблицами истинности.

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

Например, для высказывания «Река Волхов вытекает из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двойным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень».

Конъюнкция (логическое умножение). Конъюнкцией двух высказываний х, y называется новое высказывание, которое считается истинным, если оба высказывания х, y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний х,y обозначается символом , читается «х и y». Высказывания х, y называются членами конъюнкции.

Логические значения высказывания можно описать с помощью таблицы

х	y

Из определения операции конъюнкции и отрицания ясно, что высказывание всегда ложно.

Дизъюнкция (логическое сложение). Дизъюнкцией двух высказываний х, y называется новое высказывание, которое считается истинным, если хотя бы одно из высказывания х, y истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний х, y обозначается символом , читается «х или y». Высказывания х, y называются членами дизъюнкции.

Логические значения высказывания можно описать с помощью таблицы

х	y

Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.

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

Импликация высказываний х, y обозначается символом , читается «если х, то y» или «из х следует y». Высказывания х называют условием или посылкой, высказывание y – следствием или заключением, высказывание - следованием или импликацией.

Логические значения высказывания можно описать с помощью таблицы

х	y

Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.

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

Эквиваленция высказываний х, y обозначается символом , читается «для того, чтобы х, необходимо и достаточно,чтобы y» или «х тогда и только тогда, когда y». Высказывания х, y называются членами эквиваленции.

Логические значения высказывания можно описать с помощью таблицы

x	y

Конъюнкция, дизъюнкция и импликация являются бинарными, т.е. двухместными связками.

Слово «двухместная» означает, что в рассматриваемой связке предполагается наличие двух мест, куда могут быть поставлены выражения, соединяемые этой связкой.

Отрицание является одноместной (или унарной) логической операцией.

Тема 4.Формула алгебры логики. Таблица истинности.

▪ Определение формулы, подформулы, главной подформулы.

▪ Правила опускания скобок.

▪ Таблица истинности.

▪ Равносильные формулы алгебры логики.

▪ Понятия тождественно истинной(тавтологии) и тождественно ложной формул.

▪Понятия совместности, несовместности, противоположности и логического следования двух формул алгебры логики.

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

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

Если А – формула, а В – какая-либо её связная часть, которая сама тоже является формулой, то В наз. подформулой формулы А.

Главной подформулой формулы А наз. такая её подформула, которая не является частью никакой другой подформулы формулы А.

Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В,

С,...

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

В связи с этим формулы (1) могут быть записаны так:

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

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

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

Например:

х	y

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