Теорема 1: Теорема о следовании и импликации

(Здесь и далее символ будет соответствовать словесной формулировке «тогда и только тогда»)

Необходимость:

т.к. , ,

или ,

Достаточность:

Значит ,

Обобщение теоремы 1:

Г, Г , где Г=

Следствие:

 

Равносильность

Равносильность формулы В формуле А будем обозначать:

Формула А равносильна формуле В, если в любой интерпретации I. В случае логики высказываний формулы равносильны, если их таблицы истинности одинаковы, что используется для доказательства равносильности.

Основные формулы равносильности

1) – идемпотентность

2) , – коммутативность

3) – ассоциативность

4) – дистрибутивность

5)Законы де Моргана

Для алгебры предикатов необходимо добавить закон коммутативности для кванторов

и законы де Моргана для кванторов

Отношение равносильности связано с отношением следования

Теорема 2:

Необходимость:

или

Достаточность: в обратную сторону

Теорема 3: связывает отношение равносильности с операцией эквивалентности

Следствие:

Теорема 4: Теорема об эквивалентной замене

Если и есть C, в которое A входит в качестве подформулы,

C_B – формула, в которой все вхождения формулы А заменены на формулу В.

Эта теорема позволяет изменять цепочки формул без изменения их истинностного значения.

Пример

Булевы функции и нормальные формы

 

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

Логическое выражение:

Bⁿ B

2.1 Способы задания

Задание логической функции с помощью таблицы

Каждая логическая функция м.б. задана с помошью таблицы.

Пример: Задана некая булева функция.

X	Y	Z	F(x,y,z)

 

Всего 2ⁿ логических наборов переменных.

Сколько м.б. различных булевых функций от n переменных?

2ⁿ-количество различных упоряд. наборов из n переменных. Логическая функция от n переменных м.б. задана как 2ⁿ различных наборов, при этом каждому набору должно соответсвовать одно из двух значений.

Таким образом, при n=1, получаем 2²=4 лог. Функций f(x).

x	x

 

При n=2,получаем 16 функций.

x

y

(x)

(y)

x

y

|

(x)– константа х (y)– константа y

x – отрицание х y – отрицание y

Константа 0 1 – константа 1

- конъюнкция – Дизъюнкция

- Импликация - эквивалентность

- сравнение x>y - сравнение x<y

- исключающее или - обратная импликация

| - штрих Шеффера - стрелка Пирса

 

Задание логической функции с помощью формулы

Логическую функцию можно задать с помощью формул и бинарных операций.

Пример:

У нас есть некая бинарная функция и.

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

Вывод:любая функция может быть задана как таблицей, так и формулой.

 

Унарные и бинарные операции

Рассмотрим свойства унарных и бинарных операций:

Коммутативность

Коммутативными называют логические функции или логические операции, если они обладают следующим свойством:

x # x = y # x, где # - &, v, ~, |, ↓, +

 

Ассоциативность

 

(x # y) # z = x # (y # z), где # - &, v, ~, +

 

Дистрибутивность

x # (y Ъ z) = (x # y) Ъ (x # z), где #,Ъ - (&, v), (v,&),(&, +)

 

Обратные операции

(x#y)=xЪy, где #,Ъ - (&,|), (v,↓), (>,→), (<,←), (~,+)

Бинарное отрицание меняет логическую операцию на обратную.

 

Сведение к нескольким операциям

 

В частности все бинарные операции и логические функции могут быть сведены к трем операциям: .

Преобразования:

а) Все логические функции могут быть выражены через

б) через

в) через

г) можно выразить одной

д) через :

Множество функций является полным, если можно выразить все другие функции через функции этого множества.

Как определить какое множество функций является полным? Ответ на вопрос дает теорема Поста.

Теорема Поста

 

Введем 5 различных классов функций:

1) F₀ – функции сохраняющие «0».

:

При нулевых значениях аргумента, имеют значение- ноль.

 

2) F₁ – функции сохраняющие «1».

В случае,когда все значения аргумента=1,значение фнкции=1.

 

3) F ₂– монотонные функции.

n-местная логическая функция принадлежит классу монотонных функций, если у нас есть 2 набора , причем , а это значит, что тогда значение .

Т.е. если набор увеличивается, значение функций также должно увеличиваться, поэтому функция монотонная.

 

4) F ₃ – линейные функции.

где C₀ ….C_n –являются булевыми константами (0 или 1).

 

5) F ₄– самодвойственные функции.

Двойственной функцией называется функция вида:

Самодвойственной функцией называется функция двойственная самой себе.

 

Теорема Поста.

Есть множество функций. Множество функций является полным, если можно выразить все другие функции через функции этого множества.

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

Нормальные формы