Лекция дискрет 09

Переменная xi в функции f (x1, x2, … ,xi-1, xi, xi+1, … , xn) называется фиктивной переменной, если выполняется

равенство

f (x1, x2, … ,xi-1, 0, xi+1, … , xn) = f (x1, x2, … ,xi-1, 1, xi+1, … , xn)

при любых значениях переменных x1, x2, … ,xi-1, xi+1, … , xn

f (x1, x2, … ,xi-1, xi, xi+1, … , xn) = g (x1, x2, … ,xi-1, xi+1, … , xn)

Функция g получена из f удалением фиктивной переменной

Функция f получена из g введением фиктивной переменной

Логические функции f и g называются равными, если они могут быть получены друг из друга удалением или введением (возможно, неоднократным) фиктивной переменной

Примеры фиктивных переменных и равных функций

Логическая формула глубины k над множеством логических функций Σ = { f1, f2, … , fm, … }

1. Символы переменных x1, x2, … , xn, … - логические формулы глубины 0 над множеством логических функций Σ.

2. Пусть F1, F2, … , Fni – логические формулы глубины не более k над множеством логических функций Σ, причём хотя бы одна из них имеет глубину ровно k. Пусть также

fi ( x1, x2, … , xni ) Σ – логическая функция.

Тогда fi ( F1, F2, … , Fni ) – логическая формула глубины (k+1) над множеством логических функций Σ.

3. Других логических формул над множеством логических функций Σ нет.

В логической формуле fi ( F1, F2, … , Fni ):

F1, F2, … , Fni - подформулы

fi – внешняя (главная) операция формулы

Формула глубины 4 над множеством логических функций Σ = { , , , , & }

(( x y ) ( x y )) & (( x y ) ( x y )) 4

(( x y ) ( x y )) и (( x y ) ( x y )) - подформулы

& - главная операция

Логические формулы, представляющие одну и ту же логическую функцию – эквивалентные или равносильные

Логическая формула, представляющая константу 1 (φ3 или ψ15) - тавтология

Логическая формула, представляющая константу 0 (φ0 или ψ0) - противоречие