Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

закон сокращения

Появляется возможность упрощать и преобразовывать БФ к требуемому виду.

§ 2. Нормальные формы БФ.

Введем некоторые стандартные виды БФ, к которым будем их преобразовывать.

Определение: Выражение вида (отрицание может стоять на любых местах) называется элементарной конъюнкцией (ЭК).

Определение: ЭК называется правильной, если в ней переменные не повторяются.

ЭК называется полной, если в ней участвуют все n переменных.

Пример:

x,y,z – три переменные. Тогда

- Э К (правильна, но не полна).

- ЭК (правильна и полна).

- ЭК (не правильная, но полная)

Определение: Дизъюнкция нескольких ЭК называется дизъюнктивной нормальной формой (ДНФ). Если к тому же все ЭК правильны и полны, то ДНФ называется совершенной (СДНФ).

Примеры:

x,y,z,t – четыре переменные. Тогда

– ДНФ (не совершенная).

– СДНФ.

Теорема: Всякая БФ может быть представлена в виде СДНФ и притом единственным образом.

Доказывается с помощью таблицы истинности произвольной БФ.

При большом количестве переменных длина таблицы очень велика для работы с ней без применения компьютера. Поэтому, возникает проблема непосредственного преобразования данной формулы в СДНФ, не используя таблицу.

Для этого разработан естественный алгоритм:

1. Добьёмся, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания над аргументами (с помощью тождеств 1–8).

2. Раскроем скобки по тождеству 9 и получаем ДНФ.

3. Делаем все ЭК правильными (с помощью вторых частей тождеств 10 и 11).

4. Делаем все ЭК полными (если нет Х, то введём его искусственно, домножив на

число согласно тождеству 11).

Возвращаемся к шагу 2.

5. Через конечное число циклов получим СДНФ.

6. Ликвидируем одинаковые члены (с помощью тождества X Ú X=X, то есть из двух или нескольких одинаковых ЭК оставляем одну).

Аналогично вводится другая нормальная форма – СКНФ.

Определение. Выражение вида (отрицание может стоять на любых местах) называется элементарной дизъюнкцией (ЭД).

Конъюнкция нескольких ЭД называется КНФ.

Если к тому же все ЭД правильны и полны, то она называется СКНФ.

Пример:

x,y,z,t – четыре переменные. Тогда

– КНФ (не совершенная).

– СКНФ.

Мы научимся получать СКНФ с помощью СДНФ, не используя ни таблиц истинности, ни новых алгоритмов. Единственная идея – превращать дизъюнкции в конъюнкции и наоборот.

§ 3. Двойственность БФ.

Определение: Пусть дана БФ f(x₁, …,x_n). Двойственной к ней называется БФ f*, заданная формулой .

Сразу же заметим, что из тождества 1 вытекает, что всегда , то есть двойственную к двойственной БФ искать уже не надо – она всегда равна исходной функции.

Примеры вычисления двойственных БФ:

1) Для будет .

Двойственной к дизъюнкции является конъюнкция.

Так как (f*)*=f, то верно и обратное: двойственной к конъюнкции является дизъюнкция.

2) Для будет .

Итак, отрицание само себе двойственно (как говорят, самодвойственно).

3) Для будет .

Теорема: (закон двойственности) Двойственная к композиции БФ (т.е. сложной функции) - есть соответствующая композиция двойственных функций.

Пример: Пусть f=g Ú h – композиция g, h и дизъюнкции.

Тогда по закону двойственности f*=g* Ù h*.

Следствие 1: Композиция самодвойственных функций также самодвойственна.

Следствие 2: Если БФ является композицией дизъюнкций, конъюнкций и отрицаний, то для получения двойственной достаточно заметить дизъюнкции на конъюнкции и наоборот.

Пример: Если , то ..

Следствие 3: Двойственная к СДНФ является СКНФ.

Вывод: Чтобы получить СКНФ для данной функции f, следует

1. Найти двойственную БФ f*.

2. Привести f* к СДНФ.

3. Ещё раз взять двойственную, так как (f*)*=f, то получим СКНФ для f.

§4.5 Арифметический подход к БФ.

Мы уже заменили конъюнкцию умножением, попытаемся ввести сложение:

Ясно, что 0+0=1, 0+1=1, 1+0=1, но чему равно 1+1?

Альтернатива: либо принять 1+1=1, либо 1+1=0.

В первом случае мы получим дизъюнкцию,

Во втором – исключающее «или».

Исторически победил второй подход

Итак:

То есть x+y=x Δ y.

Такое сложение совпадает с известным в теории чисел сложением по модулю 2:

X+Y mod 2 – это остаток деления на числа x+y на 2.

Заметим, что всегда x+x=0, f+f=0.

Определение: Любая композиция сложения, умножения и констант называется многочленом.

Примеры: x+y+1, xy+x+1, xyz+xy+z, x+x+y+y, xy+yx+1, 1x+0=x.

Определение: Многочленом Жегалкина называется функция вида , где суммирование ведётся по некоторому множеству различных наборов (i₁, i₂, …, i_k),

в каждом из которых ни один индекс не повторяется.

Пример: xxy+xyy+x – не многочлен Жегалкина;

x+y+1 – многочлен Жегалкина.

Теорема: Всякая БФ может быть представлена в виде многочлена Жегалкина и притом единственным образом.

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

Мы уже знали, что любую БФ можно выразить через основные логические операции (отрицание, дизъюнкция и конъюнкция). Представим основные логические операции в виде многочленов Жегалкина:

xy – готовый многочлен Жегалкина;

– многочлен Жегалкина;

– многочлен Жегалкина.

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

Упрощая его получим многочлен Жегалкина.