ЕГЭОГЭЕНТ
РУҚА
Задание № 23 · ЕГЭ

Полная система логических функций

Набор операций, с помощью которого можно записать любую булеву функцию
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

Булевы функции принимают и возвращают только значения 0 и 1. Система считается полной независимо от того, насколько длинными получаются выражения. Важно лишь, что нужную функцию принципиально можно построить. Понятие рассматривается в рамках булевой алгебры, а сами операции изучаются на странице логические операции.

Примеры полных систем

  • \({\neg, \land\u007d\) — отрицание и конъюнкция («НЕ» и «И»);
  • \({\neg, \lor\u007d\) — отрицание и дизъюнкция («НЕ» и «ИЛИ»);
  • \({|\u007d\) — одна операция Шеффера, или NAND: \(A|B=\neg(A\land B)\);
  • \({\downarrow\u007d\) — стрелка Пирса, или NOR: \(A\downarrow B=\neg(A\lor B)\).
\[\forall f\;\exists F:\quad f(x_1,\ldots,x_n)=F(x_1,\ldots,x_n),\quad F\text{ построена только из операций системы}\]
№
Пример: почему NAND — полная система

Обозначим NAND через \(A|B\). Отрицание выражается так: \(\neg A=A|A\). Затем конъюнкция: \(A\land B=\neg(A|B)=(A|B)|(A|B)\). Значит, через NAND можно получить операции «НЕ» и «И», а через них — любую булеву функцию.

!
Не путайте с набором операций в конкретной схеме

Полная система не означает, что каждая операция набора обязательна в каждом выражении. Например, система \({\neg,\land}\) полна, хотя для некоторых функций достаточно только отрицания или только конъюнкции.

Проверьте себя

Какая из систем является полной?

Главное за минуту

Главное

  • Полная система позволяет выразить любую булеву функцию.
  • Классические примеры: \({\neg,\land}\), \({\neg,\lor}\), NAND и NOR.
  • Чтобы доказать полноту системы, достаточно показать, что из неё выражаются операции, образующие известную полную систему.