Главная | Обратная связь | Поможем написать вашу работу!

Теорема о замене подформул на эквивалентные

Пусть N Î< M > и имеет вид: N (x ₁,..., x_n) = g (G ₁,... G_i,..., G_m). Пусть подформула G_i ~ G_i ¢, тогда формула N (x ₁,..., x_n) = g (G ₁,..., G_i,..., G_m) эквивалентна формуле N ¢(x₁,..., x_n) = g (G ₁¢,..., G_i ¢,..., G ¢ _m).

Доказательство. Формулы N и N ¢ эквивалентны, если реализуют одну и ту же функцию. Согласно построению функции, реализующей формулу имеем:

N (x ₁,..., x_n) = g (f ₁(x ₁,..., x_n),..., f_i (x ₁,..., x_n),..., f_m (x ₁,..., x_n)),

N ¢ (x ₁,..., x_n)= g (f ₁¢ (x ₁,..., x_n),..., f_i ¢(x ₁,..., x_n),..., f_m ¢ (x ₁,..., x_n)).

По условию G_i ~ G_i ¢, следовательно на наборе (a ₁,..., a_n) имеем f_i (a ₁,..., a_n) = = f_i ¢(a ₁,..., a_n) следовательно, на любом наборе (a ₁,..., a_n)значения функции g (f ₁,..., f_i,..., f_m) и g (f ₁¢,..., f_i ¢,..., f_m ¢) совпадают. Получим N ~ N ¢.

Некоторые свойства элементарных функций

1. Идемпотентность & и Ú: х & x = x, x Ú x = x.

2. Коммутативность &,Ú,Å,|,~, .

3. Ассоциативность &,Ú,Å,~, поэтому в формулах вида xyz можно не ставить никаких скобок.

4. Дистрибутивность:

а) & по отношению к Ú: x &(y Ú z)= xy Ú xz,

б) Ú по отношению к &: x Ú(y & z)=(x Ú y)&(x Ú z),

в) & по отношению к Å: x (y Å z)= xy Å xz.

5. Инволюция: = х.

6. Правило де Моргана: = & и = Ú .

7. Законы действия с 0 и 1:

x Ú0= x, x Ú1=1, x Ú =1, x &0=0, x &1= x, x & =0, x Å1= , x Å0= x.

8. Самодистрибутивность импликации: x (y z)=(x y) (x z).

Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.

Проверим для примера самодистрибутивность импликации: x (y z)=(x y) (x z).

x	y	z	y z	x (y z)	x y	x z

Принцип двойственности

Определение 1. Функции f *(x ₁,..., x_n) называется двойственной к функции f (x ₁,..., x_n), если f *(x ₁,..., x_n) = ( ₁,..., _n).

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x f f *

Функции f (x) = x и g (x) = двойственны сами себе:

x f f * g g *

так как f *(0)= (1).

Определение 2. Если f *(x ₁,..., x_n) = f (x ₁,..., x_n), то f (x ₁,..., x_n) называется самодвойственной.

Пример 2. Покажем, что f (x ₁, x ₂, x ₃)= x ₁Å x ₂Å x ₃– самодвойственна:

x ₁	x ₂	x ₃	f	f *

Если f *– самодвойственна, то ( ₁,..., _n) = f (x ₁,..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 3. Покажем, что функция х ₁Ú х ₂двойственна к x ₁& x ₂, функция х ₁ х ₂ двойственна к функции x ₁| x ₂.

x ₁ x ₂ f = х ₁Ú х ₂ f * g = x ₁| x ₂ g *= x ₁ x ₂

0 0 0 1 1 0 1 1

Теорема о двойственных функциях

Если f * двойственна к f, то f двойственна к f *.

Доказательство. f *(x ₁,..., x_n) = ( ₁,..., _n). Найдем двойственную функцию к f *, т.е. (f *(x ₁,..., x_n))* = ( ( ₁,..., _n))* = ( ₁,..., _n) = f (x ₁,.., x_n).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

Принцип двойственности

Теорема: Пусть функция h (x ₁,..., x_n) реализована формулой h (x ₁,..., x_n) = = g (G ₁,..., G_m) = g (f ₁(x ₁,..., x_n),..., f_m (x ₁,..., x_n)), где какие-то переменные могут быть фиктивными. Тогда h *(x ₁,..., x_n) = g *(f ₁*(x ₁,..., x_n),..., f_m *(x ₁, …, x_n)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство. h *(x ₁,..., x_n) = ( ₁,..., _n) = (f ₁( ₁,..., _n),..., f_m ( ₁,..., _n)) = ( ₁( ₁,..., _n),..., ( ₁,..., _n)) = g ((),..., (() = g *(f ₁*(x ₁,..., x_n),..., f_m *(x ₁,..., x_n)), что и требовалось доказать.

Если функция h (x ₁,..., x_n) реализуется формулой N [ f ₁,..., f_n ], то формулу, полученную из N заменой f_i, входящих в нее, на f_i * и реализующую функцию h *(x ₁,..., x_n), будем называть двойственной и обозначать N *(x ₁,..., x_n).