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 принимают одинаковые значения истинности, а значит они равносильны .