Полнота систем булевых функций

Алгоритм определения всех посылок, логическим следствием которых является данная формула

Алгоритм определения всех логических следствий из данных посылок

Шаг 1. Образовать конъюнкцию всех посылок X ₁, X ₂,..., X_n.

Шаг 2. Полученную конъюнкцию привести к СКНФ.

Шаг 3. Множество всех формул, равносильных следствиям из данных посылок, образуют произведения сомножителей СКНФ, взятых по одному, по два и так далее.

Пример. Найти все следствия из посылок `XÚY и`XÙYÚX ÙY.

Образуем конъюнкцию посылок и найдем ее СКНФ.

(`X Ú`Y)Ù(`X Ù Y Ú X Ù`Y)º(`X Ú`Y)Ù(X Ú Y)Ù(`X Ú`Y)º

º(`X Ú`Y)Ù(X Ú Y) – СКНФ. Тогда следствиями являются `XÚY; X Ú Y; (`X Ú`Y)Ù(X Ú Y).

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

Шаг 1. Данную формулу привести к СКНФ.

Шаг 2. Составить ее произведения с каждым из недостающих до соответствующей полной СКНФ множителей – по одному, по два и так далее (под полной понимается СКНФ тождественно ложной формулы с теми же переменными).

Пример. Следствием каких посылок является импликация X ® Y?

Для импликации X ® Y СКНФ имеет вид. Соответствующая полная СКНФ имеет вид

.

Образуем всевозможные произведения с недостающими сомножителями:

(`X Ú Y)Ù(X Ú Y) º Y;

(`X Ú Y)Ù(X Ú`Y) º X«Y;

(`X Ú Y)Ù(`X Ú`Y) º`X;

(`X Ú Y)Ù(X Ú Y) Ù (X Ú`Y) º X Y;

(`X Ú Y)Ù(X Ú Y) Ù(`X Ú Y) º XY;

(`X Ú Y) Ù (X Ú`Y) Ù(`X Ú`Y) º XY;

(`X Ú Y)Ù(X Ú Y) Ù(`X Ú Y) Ù(`X Ú`Y) º 0.

Ранее отмечалось, что любая функция алгебры логики может быть выражена в виде формулы через элементарные функции x ̅, x ₁ Ù x _2, x ₁ Ú x ₂. Однако, такими свойствами обладают и другие системы элементарных функций.

Система функций {ƒ₁,ƒ₂,…ƒ_n} из P ₂ (множество всех булевых функций) называется (функционально) полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Примеры фундаментально полных систем:

1) P ₂ – множество всех булевых функций – полная система

2) Система { x ̅, x ₁ Ù x _2, x ₁ Ú x ₂} – полная система

Заметим, что система {0,1} не является полной.

Теорема. Пусть даны две системы функций из P ₂ . A = {ƒ₁, ƒ₂…} и B = { g ₁, g ₂…}, относительно которых известно, что система функций A полна и каждая ее функция выражается в виде формулы через функции системы B. Тогда система B является полной.

Опираясь на эту теорему можно установить полноту ряда систем и тем самым расширить список примеров полных систем.

3) Система { x ̅, x ₁ Ù x ₂} является полной, т.к. известно, что 2) полна и.

4) Система { x ̅, x ₁ Ú x ₂} является полной, т.к. полна система 2) и, кроме того,.

5) Система { x ₁ | x ₂} является полной, т.к. взяв за систему A систему 3), а за систему B систему 5) и определив и.

6) Система {0, 1, x ₁ x ₂, x ₁ Å x ₂} является полной. Для этого за систему A берется система 3), а за B – система 6).

При этом: x ₁ Å 1 = x ̅_1, x ₁ x ₂ = x ₁ Ù x ₂

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

Дата добавления: 2014-01-11