Элементы математической логики. Исчисление высказываний

ПЛАН

1. Определение формулы исчисления высказываний.

2. Алгебра высказываний.

3. Равносильность формул исчисления высказываний. Конъюнктивная нормальная форма.

4. Дизъюнктивная нормальная форма. Проблема разрешимости.

5. Совершенная конъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма.

Литература

1. ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕН

ИЯ ВЫСКАЗЫВАНИЙ

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

1. Пропозициональные переменные. Их будем обозначать малыми буквами латинского алфавита с индексами или без них: x, у, х, ., p, q, . Различные буквы обозначают разные суждения, внутренняя структура суждений нас интересовать не будет. Суждения, обозначенные пропозициональными переменными, будут называться высказываниями. Будем полагать, что высказывания удовлетворяют закону исключенного третьего и закону непротиворечия, т.е. каждое высказывание либо истинно, либо ложно. Так что каждая переменная у нас будет принимать два значения: значения «истина» будем обозначать «1», а значение «ложь» – «0».

2. Константы или логические связи – «―», «Ù», «Ú», «®», «º».

3. Скобки: «(» - левая скобка и «)» - правая скобка.

С помощью констант (связок) атомарные высказывания соединяются в более сложные высказывания. Так из двух высказываний p и q с помощью констант образуются высказывания

`p - читается «не-р»

`q - читается «не-q»

pÙq – читается «р и q»

pÚq – читается «р или q»

р®q - читается «если р, то q»

рºq - читается «р тогда и только тогда, когда q»

Сложное высказывание, образованное с помощью знака «¯» называется отрицанием, знака - «Ù» - конъюнкцией, знака «Ú» - дизъюнкцией, знака «®» - импликацией, знака «º» - эквивалентностью. Переменные и сложные высказывания, образованные из них посредствам многократного применения логических связок и скобок называются формулами исчисления высказываний, если они удовлетворяют трем условиям:

1) Пропозициональная переменная есть формула

2) Если φ и ψ – формулы, то (`φ), (`ψ), (φ) Ù ( ψ), (φ) Ú ( ψ), (φ) ® ( ψ), (φ) º ( ψ) – формулы. Входящие в эти формулы, формулы (φ) и ( ψ) мыбудемназывать подформулами этих формул.

3) Всякая формула есть либо пропозициональная переменная или образуется из пропозициональных переменных последовательным применением правила 2).

Во избежание ошибок принимаются следующее соглашение об употреблении малых греческих букв φ,ψ,γ, . . . Эти буквы не являются знаками языка исчисление высказываний и принципиально без них можно было бы обойтись. Они служат лишь для того, чтобы облечь в краткую форму сообщение об исчислении. При таких сообщениях через φ,ψ,γ, . . . обозначаются любые формулы, точный формальный вид которых остается неопределенным. Так, (φ)®( ψ) заменяет любую формулу, например ((p)Ù(q))→(p) или ((p) → (q))→(p).

Для того, чтобы избежать слишком, большое количество скобок принимаются следующее соглашение:

1) Опускаются скобки, объемлющие отдельные переменные.

2) Полагают, что знак конъюнкций связывает сильнее, чем дизъюнкции и в формулах (φÙψ) Ú γ, γÚ(φÙψ) скобки можно опускать. Аналогичные соглашения принимается относительно других знаков, т.е. считается, что знак «Ù» связывает сильнее, чем знаки «Ú», «®», «º», знак «Ú» сильнее, чем знаки «®», «º», знак «®» сильнее, чем знак «º». Правда, для легкости чтения формул мы будем иногда отступать от этих соглашений.

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

2. АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

1) Атомарное высказывание, т.е. переменная, может принимать два значения «1» или «0».

2) Значение формул образованных неоднократным применением логических связок к атомарным высказываниям, задается таблицей:

 Скачать реферат