Элементы математической логики

 

Высказыванием называется всякое утверждение (повествовательное предложение), про которое всегда определенно и объективно можно сказать, является ли оно истинным или ложным. Высказывания будем обозначать заглавными латинскими буквами: A, B, C и т.д. Будем полагать значение истинного высказывания равным 1, а ложного – равным 0.

 

Высказывание  называется отрицанием высказывания А, если оно истинно, когда А ложно, и ложно, когда А истинно:

 

Отрицание соответствует частице «не».  Символ  читается «не А» или «не верно, что А».

 

Дизъюнкция АÚВ – сложное высказывание, которое ложно тогда и только тогда, когда оба высказывания А и В одновременно ложны:

Операция дизъюнкция соответствует соединению их с помощью союза «или».

 

Конъюнкция АÙВ  – сложное высказывание, которое истинно тогда и только тогда, когда оба высказывания А и В одновременно истинны:

Операция конъюнкция соответствует соединению их с помощью союза «и».

 

Импликация высказываний А и В (А®В) – сложное высказывание, которое истинно всегда, кроме случая когда А – истинно, а В – ложно:

Импликация соответствует объединению двух высказываний с помощью союза «если …, то …».

 

Эквивалентность высказываний А и В (А«В) – сложное высказывание, которое истинно, когда А и В одновременно либо истинны, либо ложны и ложно во всех других случаях. Эквивалентность определяется следующей таблицей истинности:

Эквивалентность обозначается символом «, либо ~; читается: "А эквивалентно В", либо "А равносильно В", либо "А тогда и только тогда, когда В", либо "В, если и только если А". Эквивалентность примерно соответствует употреблению выражения "тогда и только тогда, когда".

 

Порядок выполнения логических операций: сначала выполняется операция отрицания Ø, затем конъюнкция Ù и дизъюнкция Ú (они равноправны), затем импликация ® и, последней, эквивалентность «.

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

 

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

 

Равносильные формулы логики высказываний:

АÚВº ВÚА,	АÙВº ВÙА	Коммутативные законы
АÚ(ВÚС)º (АÚВ) Ú С,	АÙ(ВÙС)º (АÙВ) Ù С	Ассоциативные законы
АÚ(ВÙС)º (АÚВ) Ù (АÚС),	АÙ(ВÚС)º (АÙВ) Ú (АÙС)	Дистрибутивные законы
А Ú А º А,	А Ù А º А	Законы идемпотентности
АÚ(АÙВ)º А,	АÙ(АÚВ)º А	Законы поглощения
,		Законы де Моргана
А Ú 0 º А,	А Ù 1 º А	Операции с константами[1]
А Ú 1 º 1,	А Ù 0 º 0

 

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

 

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

1.     ½=  А. Закон силлогизма

½=    .

2.     Modus ponens  (лат.)

½=    .

3.     Закон контрапозиции

½=    .

4.     Закон исключения третьего 

½=    .

5.     Закон противоречия 

½=    .

6.     Закон двойного отрицания

½=   « А.

 

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

½=  В.