Высказывания бывают простые и составные, конкретные и переменные. Высказывание наз-ся конкретным, если известна его словесная форма

1. Основным понятием мат логики явл-ся понятие высказывания. Высказыванием называют повествовательное предложение, относительно которого имеет смысл утверждать, что оно явл-ся истинным или ложным.

Высказывания бывают простые и составные, конкретные и переменные. Высказывание наз-ся конкретным, если известна его словесная форма.

Любая буква латинского алфавита, вместо которой может быть поставлено конкретное высказывание наз-ся высказывательной переменной.

Высказывание наз-ся простым, если в нем нельзя выделить часть, которая сама является высказыванием, не совпадающим по смыслу с исходным. В противном случае высказывание наз-ся составным.

Логические связки: 1)не; неверно, что 2)и; а; но 3)или; либо 4)если, то 5)титт, когда.

Указанным логическим связкам соответствуют операции над высказываниями:

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

2.конъюнкцией двух высказываний a и b наз-ся новое высказывание, обозначаемое , которое истинно титт, когда оба высказывания истинны и ложное во всех остальных случаях.

3.дизъюнкцией двух высказываний a и b наз-ся новое высказывание, обозначаемое , которое ложно титт, когда ложны оба высказывания и истинное во всех остальных случаях.

4.импликацией двух высказываний a и b наз-ся новое высказывание, обозначаемое , которое ложно лишь в случае, когда 1-е высказывание истинно, а 2-е ложно.

5.эквиваленцией двух высказываний a и b наз-ся новое высказывание, обозначаемое , которое истинно титт, когда оба высказывания принимают одинаковые значения истинности.

 

2. Формулой алгебры высказываний будем называть: 1)любое конкретное или переменное высказывание; 2)если a и b-формулы, то формулами также явл-ся ; 3)других формул, кроме определенных пунктами 1)-2) не существует.

Конкретный набор значений истинности для высказывательных переменных, входящих в запись формулы будем называть логической возможностью формулы. Т.к. для формулы от одной переменной сущ-ет две логич возможности, то от 2-х переменных-4,…, для формулы от n переменных .

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

Две формулы F и G наз-ют равносильными ( ), если они принимают одинаковые значения истинности каждой своей общей логической возможности.

Теорема об отношении равносильности. Отношение равносильности явл-ся отношением эквивалентности. Док-во: действительно, для любых 3-х произвольных формул A,B,C согласно равносильности формул вып-ся: 1) ; 2) ; 3)

 

3.Формулы алгебры высказываний можно разделить на 3 класса:тавтологии, противоречие и выполнение формулы.

Формула АВ наз-ся тавтологией или тождественно истинной, если она истинна в каждой своей логической возможности. ( )

Формула АВ наз-ся противоречием или тождественно ложной, если она ложна в каждой своей логической возможности. ( )

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

Теорема (о связи равносильности формул и тавтологий). .

Док-во: (необх)Пусть , тогда в каждой своей общей логической возможности эти формулы принимают одинаковые значения истинности, а значит, согласно определению эквивалентности . (дост) Пусть , тогда согласно определению эквивалентности F и G принимают одинаковые значения истинности, а значит они равносильны .

Законы логики.

2.законы идемпотентности: 3.законы коммутативности: 4.законы ассоциативности: