Нормальные формы и теорема Поста

СДНФ и СКНФ

СДНФ (совершенная дизъюнктивная нормальная форма): дизъюнкция минтермов. Минтерм — конъюнкция всех переменных (с отрицаниями или без), соответствующая строке таблицы истинности с f=1.

f(x,y) = (x AND NOT y) OR (NOT x AND y) = x⊕y (XOR).

СКНФ (совершенная конъюнктивная нормальная форма): конъюнкция макстермов (дизъюнкции для строк с f=0).

Теорема Поста о полноте

Замкнутый класс функций — множество F, замкнутое относительно суперпозиции (подстановки, отождествления переменных).

Пять классов Поста:

• T₀: функции, сохраняющие 0 (f(0,...,0)=0)
• T₁: функции, сохраняющие 1 (f(1,...,1)=1)
• S: самодвойственные (f(¬x₁,...,¬xₙ) = ¬f(x₁,...,xₙ))
• M: монотонные (xᵢ ≤ yᵢ → f(x) ≤ f(y))
• L: линейные (над GF(2))

Теорема Поста: Система F функций полна тогда и только тогда, когда она не содержится ни в одном из пяти классов.

Применения

Минимизация булевых функций — задача логического синтеза. Метод Куайна–Маккласки: нахождение минимальной КНФ/ДНФ. Карта Карно — графический метод для функций до 4-5 переменных.

В САПР: синтез цифровых схем = минимизация булевых функций с ограничениями на число вентилей.

Пять замкнутых классов Поста: подробнее

Каждый замкнутый класс имеет содержательный смысл. T₀ (сохраняющие 0) содержит AND, OR, XOR, константу 0, но не NOT (NOT(0)=1). T₁ (сохраняющие 1) содержит AND, OR, но не XOR (XOR(1,1)=0). S (самодвойственные) — функции, для которых при одновременном инвертировании всех аргументов значение инвертируется: f(¬x) = ¬f(x). NOT самодвойственна: NOT(¬x) = ¬(NOT x). Мажорность M(x,y,z) = «хотя бы два из трёх» самодвойственна. M (монотонные) — значение не уменьшается при переходе от 0 к 1: AND, OR, константы монотонны, NOT — нет. L (линейные) — функции вида c₀ ⊕ c₁x₁ ⊕ ... ⊕ cₙxₙ над GF(2): XOR, NOT, тождественная. AND нелинейна.

Система {AND, OR, NOT} полна: NOT ∉ T₀, AND ∉ S, OR ∉ L. {NAND} полна: одна функция нарушает все пять классов. {XOR, AND, 1} полна: AND нарушает S и T₀; проверьте остальные.

Сложность распознавания полноты

Проверка теоремы Поста для конкретной системы функций — алгоритмически разрешимая задача полиномиальной сложности: нужно проверить вхождение каждой функции в каждый из пяти классов. Но задача нахождения минимальной полной системы в данном классе функций — NP-трудная.

Существуют функционально полные одноэлементные системы: {NAND}, {NOR}. Процессоры реально строятся из NAND-вентилей: они универсальны, дёшевы в производстве и реализуются в CMOS-технологии с минимальным числом транзисторов. NAND(x,y) = ¬(x∧y): NOT(x) = NAND(x,x); AND(x,y) = NAND(NAND(x,y), NAND(x,y)); OR(x,y) = NAND(NAND(x,x), NAND(y,y)).

Полиномы Жегалкина

Каждую булеву функцию можно единственным образом записать в виде полинома Жегалкина — полинома над GF(2) с коэффициентами 0 или 1: f(x₁,...,xₙ) = c₀ ⊕ c₁x₁ ⊕ ... ⊕ c_{12}x₁x₂ ⊕ ... ⊕ c_{12...n}x₁x₂...xₙ. Линейные функции (класс L Поста) — это в точности те, у которых в полиноме Жегалкина нет слагаемых степени ≥ 2. Этот критерий даёт алгоритм проверки линейности за O(2^n) через треугольник разностей (аналог треугольника Паскаля).

Теорема о полноте для многозначных логик

В трёхзначной логике Лукасевича (значения: 0, 1/2, 1) классическая двузначная полнота нарушается — {NAND} не является полной. Критерии полноты для многозначных логик сложнее и зависят от структуры. В нечёткой логике (значения из [0,1]) роль AND играет t-норма (min или умножение), OR — t-конорма (max или вероятностная сумма), NOT — инволюция. Полнота зависит от выбора операций.

Квантовые логические вентили: обобщение булевых

Квантовые вентили действуют на кубиты — суперпозиции |0⟩ и |1⟩. Они представляются унитарными матрицами, а не булевыми функциями. Вентиль Адамара H: |0⟩ → (|0⟩+|1⟩)/√2 (суперпозиция). Вентиль CNOT (controlled-NOT): |x,y⟩ → |x, y⊕x⟩ — квантовый аналог XOR. Теорема Соловея-Китаева: любой квантовый вентиль приближается произведением базовых вентилей {H, T, CNOT} с экспоненциально малой ошибкой, используя O(log^c(1/ε)) вентилей. Это квантовый аналог теоремы Поста о функциональной полноте.

Квантовая запутанность и её вычислительные следствия

Запутанность (entanglement): состояние системы двух кубитов называется запутанным, если его нельзя записать как |ψ₁⟩⊗|ψ₂⟩. Пример: |Φ⁺⟩ = (|00⟩+|11⟩)/√2 — состояние Белла. Парадокс ЭПР и неравенства Белла: квантовые корреляции превосходят любую локальную скрытопеременную теорию. Квантовая телепортация: передача квантового состояния без физической передачи частицы, используя запутанность и два классических бита. Супер-плотное кодирование: передать 2 классических бита с помощью 1 кубита (при наличии запутанной пары).

Численный пример: нормальные формы и функциональная полнота

Задача: (а) Привести f(a,b)=a∧¬b в ДНФ и КНФ. (б) Проверить, полна ли {⊕,1} (XOR и константа 1).

Шаг 1 (НФ): Таблица истинности f(a,b): (0,0)=0, (0,1)=0, (1,0)=1, (1,1)=0. Один единичный минтерм: (1,0).

Шаг 2 (ДНФ): ДНФ: f = a∧¬b. КНФ: нулевые строки (0,0),(0,1),(1,1) → максдизъюнкты (a∨b), (a∨¬b), (¬a∨¬b). КНФ: f=(a∨b)∧(a∨¬b)∧(¬a∨¬b). Упрощение: (a∨b)∧(a∨¬b)=a; f=a∧(¬a∨¬b)=a∧¬b ✓.

Шаг 3 (полнота): Критерий Поста: {⊕,1} линейна (⊕ — XOR, 1 — линейная константа). Любая суперпозиция линейных функций линейна. Конъюнкция a∧b нелинейна → не реализуема.

Шаг 4: {⊕,1} НЕ функционально полна. Для полноты добавьте ∧: тогда {⊕,∧,1} полна (реализует ¬a=a⊕1, все операции). Система {NAND} полна: ¬a=NAND(a,a), a∧b=¬NAND(a,b), a∨b=NAND(¬a,¬b). Нормальные формы используются в СБИС-верификации через BDD-проверку эквивалентности схем.