Files

2.6 KiB
Raw Permalink Blame History

Логическая функция и способы её задания. Число логических функций.
Существенные и фиктивные переменные. Основные операции алгебры логики.
Логические формулы. Эквивалентность функций. Эквивалентность формул.

Логическая функция и способы её задания.

  • Логическая функция (булева) - функция, у которой каждая переменная принимает значения {0, 1} и сама функция возвращает значение из такого множества f:\{0,1\}^n \rightarrow \{0,1\}
  • Любую логическую функцию можно задать перечислением значений на всех различных наборах значений переменных.

Число логических функций.

Теорема

Существует 2^{2^n} логических функций от n переменных

Доказательство

Функция определяется набором значений и каждый набор длины 2^𝑛 из элементов 0, 1 задает некоторую функцию от 𝑛 переменных. Логических функций от n переменных имеется ровно столько, сколько существует таких наборов, тo есть 2^{2^n}

Существенные и фиктивные переменные

  • Фиктивная переменная - переменная, значение которой не зависит на значение функции
  • Существенная переменная - не фиктивная переменная (лол)

Основные операции алгебры логики

  • Отрицание: f(x) = \bar x
  • Селектор: f(x, y) = x
  • Конъюнкция: f(x, y) = x\&y
  • Дизъюнкция: f(x, y) = x|y
  • Сумма по модулю 2: f(x, y) = x \oplus y
  • Импликация: f(x,y) = x \rightarrow y
  • Эквивалентность: f(x, y) = x \equiv y

Логические формулы

Логические формулы - формулы, на основе элементарных логических функций

Эквивалентность формул

Две формулы эквивалентны, если они представляют эквивалентные функции