Понятие формулы алгебры высказываний определяется следующим образом:
Подформулой формулы Á называется любое подслово слова Á , которое само является формулой.
В §§ 1—3 будут использоваться большие латинские буквы А, В, С,… для обозначения произвольных пропозициональных переменных, а большие готические буквы Á ,V ,… для обозначения формул.
Понятие формулы алгебры высказываний определяется следующим образом:
Подформулой формулы Á называется любое подслово слова Á , которое само является формулой.
В §§ 1—3 будут использоваться большие латинские буквы А, В, С,… для обозначения произвольных пропозициональных переменных, а большие готические буквы Á ,V ,… для обозначения формул.
Будем обозначать формулу ((Á É В) & (В É Á )) через ( Á º В ).
Будем интерпретировать логические связки как функции, определенные на множестве {и , л} (истина, ложь), со значениями в том же множестве следующим образом.
Отрицание : ù и = л, ù л = и.
Конъюнкция: и & и = и, и & л = л & и = л & л =л.
Дизъюнкция: и È и = и È л = л È и = и, л È л = л.
Импликация: и É и = л É и = л É л = и, и É л = л.
Тогда каждая формула будет интерпретироваться как функция, определенная на множестве {и , л}, со значениями в этом же множестве, полученная из ù , & , È , É по правилам построения данной формулы. Такую функцию будем называть таблицей истинности данной формулы. Значением формулы Á при данных значениях переменных в множестве {и , л}называется значение функции, соответствующей формуле Á , при этих значениях переменных.
Формулы Á и В называются эквивалентными ( обозначается Á ~ В), если при любых значениях переменных значение Á совпадает со значением В. Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение и ( л ). Формула называется тождественно истинной или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение и ( л ) при всех наборах значений переменных.
Пусть Á 1, Á 2,…,Á п (п ³ 1). Будем называть конъюнкцией формул Á 1, Á 2,…,Á п формулу (…(Á 1 & Á 2) & …& Á п) и обозначать её через (Á 1 & Á 2 & … & Á п) . Будем называть дизъюнкцией формул Á 1, Á2,…,Á п формулу (…(Á 1 È Á 2) È …È Á п) и обозначать её через (Á 1 È Á 2 È … È Á п).
Элементарной конъюнкцией (дизъюнкцией) называется произвольная конъюнкция (дизъюнкция) формул, каждая из которых есть пропозициональная переменная или отрицание пропозициональной переменной.
Дизъюнктивной нормальной формой (д. н. ф.) называется произвольная дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (к. н. ф.) называется произвольная конъюнкция элементарных дизъюнкций.
Д.н.ф. (к.н.ф.) Á называется совершенной и обозначается с.д.н.ф. (с.к.н.ф.), если каждая переменная формулы Á входит в каждую элементарную конъюнкцию (дизъюнкцию) ровно один раз с отрицанием или без отрицания.
Д.н.ф. (к.н.ф., с.д.н.ф., с.к.н.ф.), эквивалентная данной формуле Á , называется д.н.ф. (к.н.ф., с.д.н.ф., с.к.н.ф.) формулы Á .