Математическая Логика (стр. 2 из 4)

2)

(коммутативность)

3)

(свойство нуля)

4)

(закон поглощения для 1)

5)

(ассоциативность)

6)

(коммутативность)

7)

(свойство нуля по умножению)

8)

(свойство нейтральности 1 по умножению)

9)

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

10)

(дистрибутивность 2)

11)

(закон поглощения)

12)

( Законы

13)

де Моргана)

14)

(закон снятия двойного отрицания)

15)

(tertium non datur – третьего не дано)

16)

(ассоциативность)

17)

18)

19)

20)

21)

(Свойства

22)

идемпотентности)

2.2 Дизъюнктивные нормальные формы.

2.2.1 Основные определения.

- конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

- элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

2.2.2 Теорема о совершенной ДНФ.

Любая булева функция

тождественно не равная 0 может быть разложена в ДНФ следующего вида:

Опр: Носитель булевой функции

.

Лемма:

1)

это элементарно

2)

возьмем набор

а)

б)

Доказательство:

, будем доказывать, что .

1) Докажем, что

. Возьмем он попадает в число суммируемых наборов и по нему будет проводиться сумирование.

2) Докажем, что

. Возьмем другой набор из

Следовательно

2.2.3 Некоторые другие виды ДНФ.

Опр:

- называется минимальной ДНФ, если она имеет - наименьшую возможную длину из всех ДНФ данной функции.

Опр:

- называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество

, которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция

и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение:

(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

3 Логические Исчисления.

3.1 Исчисления высказывания (ИВ).

3.1.1 Определения.

Опр: V – словом в алфавите А, называется любая конечная упорядоченная последовательность его букв.

Опр: Формативная последовательность слов – конечная последовательность слов и высказываний

, если они имеют формат вида:

Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь формативную последовательность.

Пример:

Опр: Аксиомы – специально выделенное подмножество формул.

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое).

a – символ переменной