LiArrowUp01

Алексеев В. Б. - Дискретная математика - Функции алгебры логики

Будем рассматривать множества

Булевы функции 02:54

Такими функциями называются отображения . Будем рассматривать только всюду определенные функции[1]

Малое входное множество компенсируется "обширным" образом, т.е. большим количеством аргументов

Способы задавать булевы функции 04:57

Функции можно задавать с помощью таблицы:

0 1 — тождественная функция — отрицание
0 0 1 0 1
1 0 1 1 0

0 0 0 0 0 1 1 1 1
0 1 0 1 1 1 1 0 0
1 0 0 1 1 0 1 0 0
1 1 1 1 0 1 0 0 1

Тут

  • — конъюнкция, и
  • — дизъюнкция, неразделительное или
  • — сумма по модулю 2, исключающее или
  • — импликация, если… то…
  • — штрих Шеффера, не И (NAND)
  • — стрелка Пирса, не ИЛИ (NOR)
  • — эквиваленция, равнозначность

Построение ФАЛ 18:41

Лемма о числе слов

В алфавите из букв можно построить слов длины

Как следствие, существует функций от переменных 25:05

Это очень много! Так, при имеем дело с порядком

Вещественная и фиктивная переменная 29:42

Переменная называется вещественной для ФАЛ, если , если ( зависит от того, какое значение принимает )
В противном случае переменную называют фиктивной

Равные ФАЛ 33:46

2 ФАЛ называются равными, если одну можно получить из другой добавляя и исключая фиктивные переменные
Но на практике просто проверяют таблицы истинности; можно и убрать все фиктивные переменные, но в случае констант фиктивны все переменные

Формула над множеством ФАЛ 43:00

Пусть — некоторое множество ФАЛ. Формулой над называют индуктивное понятие:

  1. называется формулой над
  2. , а являются либо переменными, либо формулой над . Тогда — тоже формула над
  3. Формулой над называются только те варианты, которые можно построить по предыдущим пунктам и за конечное число шагов
    Формулы же вычисляются рекурсивно

Теорема о разложении по переменным 1:02:10

59:47


Заметим, что

Теорема:

Выполняется

  1. это не связанно с инъекцией или сюръекцией)↩︎

Interactive Graph
Table Of Contents
LiArrowUp01Алексеев В. Б. - Дискретная математика - Функции алгебры логики
Способы задавать булевы функции 04:57

Построение ФАЛ 18:41
Теорема о разложении по переменным 1:02:10