18Булева алгебра логических операций. Основные эквивалентные соотношения (законы) в булевой алгебре.

Алгебра (Р₂; &, Ú, Ø), основным множеством которой является множество всех логических функций Р₂, а операциями дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических операций. Операции булевой алгебры часто называют булевыми операциями

ассоциативность aÚ(bÚc)=(aÚb)Úc, aÙ(bÙc)=(aÙb)Ùc;

коммутативность aÚb=bÚa, aÙb=bÙa;

дистрибутивность aÙ(bÚc)=aÙbÚaÙc; aÚbÙc=(aÚb)Ù(aÚc);

идемпотентность aÚa=a, aÙa=a;

двойное отрицание ØØa=a;

законы нуля (лжи) aÚ0=a, aÙ0=0, aÙØa=0;

законы единицы (истины) aÚ1=1, aÙ1=a, aÚØa=1.

де-Моргана ØaÚØb=Ø(aÙb), ØaÙØb=Ø(aÚb);

противоречия aÙØа=0;

исключенного третьего aÚØа=1

19Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

В ведем обозначения x⁰ = `x и x¹ = x. Пусть а — параметр, равный 0 или 1. Тогда x^a = 1, если x = а, и x^a = 0, если x ¹ а. Теорема. Всякая логическая функция f(x₁, …, x_n) может быть представлена в следующем виде:

где m £ n, а дизъюнкция берется по всем 2^m наборам значений переменных x₁, …, x_m.Это равенство называется разложением по переменным x₁, …, x_m.

ДНФ это дизъюнкция элементарных конъюнкций. СДНФ - каждый элемент конъюнкции содержит все переменные и элементарные конъюнкции различны. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f. Выписываются единичные наборы векторов, соедин конъюнкциями. Те переменные ,которые равны 0 ,над ними ставится отрицание. Потом конъюнкции соедин дизъюнкциями.

20ДНФ, СДНФ, КНФ, СКНФ. Процедуры приведения к ДНФ и КНФ.

ДНФ это дизъюнкция норм конъюнкций.

• 1. Все отрицания спустить до переменных с помощью де Моргана и двойного отриц.

• 2. Раскрыть скобки с помощью ассоциативности и дистрибутивности.

• 3. Удалить лишние конъюнкции и повторения переменных с помощью идемпотентности, противоречия и искл третьего.

• 4. Удалить константы с помощью законов нуля и единицы.

СДНФ - каждый элемент конъюнкции содержит все переменные и элементарные конъюнкции различны.(элементарной конъюнкцией назыв переменные, соед конъюнкцией)

КНФ конъюнкция норм дизъюнкций. Аналогично!

СКНФ – каждый элементарный дизъюнкт содержит все переменные и элементарные дизъюнкции различны.

2 1Двойственность.

Функция f₁(x₁,…, x_n) называется двойственной к функции f₂(x₁,…, x_n), если.

Отношение двойственности между функциями симметрично. Из определения двойственности ясно, что для любой функции двойственная функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной.

Примеры: дизъюнкция двойственна конъюнкции; константа 1 двойственна 0;отрицание самодвойственно;

22Алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина.

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями

алгебра Вебба A = áM, oñ; алгебра Шеффера A = áM, ½ñ; импликативная алгебра A = áM, ®, 0ñ; коимпликативная алгебра A = áM, ®, 1ñ; алгебра Жегалкина A = áM, &, Å, 1ñ.

23Полиномы Жегалкина. Процедуры приведения к ПНФ.

Полином Жегалкина — полином(многочлен) над Z2, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или.

Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде

как пример

По сравнению с ДНФ в полиноме Жегалкина отсутствуют операции ИЛИ и НЕ. Таким образом, полином Жегалкина можно получить из ДНФ, выразив операции ИЛИ и НЕ через операции Исключающее ИЛИ, И и константу 1. Для этого применяются следующие соотношения:

24Конечно-значные логики: алгебра Вебба, алгебра Поста, алгебра Россера–Тьюкетта.

Функция Вебба

Конечнозначная алгебра Вебба

алгебра Поста

дизъюнкция

цикл

алгебра Россера—Тьюкетта

конъюнкция

характеристические функции

25Исчисление высказываний как формальная система, множественность аксиоматизаций. Проблема выводимости. Прямой вывод.

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

В прямом выводе используется знание семантики тех операторов, через которые строятся аксиомы. Если из аксиомы следует что A&B, то смысл таков, что истинным будет высказывание А и В, которые войдут в цепочку вывода. В прямом выводе строится цепочка высказываний, она и будет выводом.