11
правок
Изменения
→Основные сведения
<center>
{|class="wikitable" align="center" style="widthcolor: blue; background-color:10cm#ffffcc;" bordercellpadding=1"10"
|+
!colspan="6"|Таблица истинности
|-align="center"
! <tex>x_1</tex> || <tex>x_2</tex> || <tex>...</tex> || <tex>x_n</tex> || <tex>f(x_1,x_2,...,x_n)</tex>
|-align="center"
| <tex>1</tex> || <tex>1</tex> || <tex>...</tex> || <tex>0</tex> || <tex>f(1,1,...,0)</tex>
|-align="center" style="height:0.9cm"
| <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex>
|-align="center"
Таблица значений булевых функций от одной переменной:
<center> {| borderclass="1wikitable"align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="5"|Функции от одной переменной
|-align="center"
!x
|! width="12%" | <tex>0</tex>
|! width="12%" | <tex>x</tex>
|-align="center"
!0
|<tex>0</tex>||<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
|-align="center"
!1
|<tex>0</tex>||<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|-align="center" bgcolor=#EEEEFF
!Сохраняет 0
|1✓||1✓||0||0|-align="center" bgcolor=#EEEEFF
!Сохраняет 1
|0||1✓||0||1✓|-align="center" bgcolor=#EEEEFF
!Самодвойственная
|0||1✓||1✓||0|-align="center" bgcolor=#EEEEFF
!Монотонная
|1✓||1✓||0||1✓|-align="center" bgcolor=#EEEEFF
!Линейная
|1✓||1✓||1✓||1✓
|}
</center>
Названия булевых функций от одной переменной:
<center>{| borderclass=1"wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"
!Обозначение
!Название
|-
!<tex>0</tex>
|<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
|-
!<tex>x</tex>
|<font color="black">тождественная функция, логическое "ДА", "YES"(англ.)</font>
|-
!<tex>\bar x,\ \neg x,\ x'</tex>
|<font color="black">отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)</font>
|-
!<tex>1</tex>
|<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>
|}
</center>
=== Бинарные функции ===
При <tex>n = 2</tex> число булевых функций равно <tex>{2^2}^2 = 2^4 = 16</tex>.
Таблица значений булевых функций от двух переменных:
<center>{| borderclass="1wikitable"align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="18"|Функции от одной переменной
|-align="center"
!<font color="black">x</font>||<font color="black">y</font>
|! width="5%" | <tex>0</tex>
|! width="5%" | <tex>x \land y</tex>
|! width="5%" | <tex>1</tex>
|-align="center"
!<font color="black">0</font>||<font color="black">0</font>
|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1
|-align="center"
!<font color="black">0</font>||<font color="black">1</font>
|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1
|-align="center"
!<font color="black">1</font>||<font color="black">0</font>
|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1
|-align="center"
!<font color="black">1</font>||<font color="black">1</font>
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">Сохраняет 0</font>|1✓||1✓||1✓||1✓||1✓||1✓||1✓||1✓||0||0||0||0||0||0||0||0
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">Сохраняет 1</font>|0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓||0||1✓
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">Самодвойственная</font>|0||0||0||1✓||0||1✓||0||0||0||0||1✓||0||1✓||0||0||0
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">Монотонная</font>|1✓||1✓||0||1✓||0||1✓||0||1✓||0||0||0||0||0||0||0||1✓
|-align="center" bgcolor=#EEEEFF
!colspan="2"|<font color="black">Линейная</font>|1✓||0||0||1✓||0||1✓||1✓||0||0||1✓||1✓||0||1✓||0||0||1✓
|}
</center>
Названия булевых функций от двух переменных:
<center>{| class="standardwikitable" borderalign=1"center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"
!Обозначение
!Другие обозначения
!<tex>0</tex>
|
|<font color="black">тождественный ноль, тождественная ложь, тождественное "НЕТ"</font>
|-
!<tex>x \land y</tex>
|align = center|<tex>x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y),x </tex> ''x <font color="black">И </font> <tex>y, </tex> <font color="black">И</font><tex>(x, y)''</tex> |<font color="black">2И, конъюнкция</font>
|-
!<tex>x \nrightarrow y</tex>
|align = center|<tex>x > y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)</tex>
|<font color="black">больше, инверсия прямой импликации</font>
|-
!<tex>x</tex>
|align = center|<tex>YES1(x,y),</tex> ''<font color="black">ДА1</font><tex>(x, y)''</tex> |<font color="black">первый операнд</font>
|-
!<tex>x \nleftarrow y</tex>
|align = center|<tex>x < y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)</tex>
|<font color="black">меньше, инверсия обратной импликации</font>
|-
!<tex>y</tex>
|align = center|<tex>YES2(x, y),</tex> ''<font color="black">ДА2</font><tex>(x, y)''</tex> |<font color="black">второй операнд</font>
|-
!<tex>x \oplus y</tex>
|align = center|<tex>x + _2 y,\ x \not = y,\ x >< y,\ x <> y,\ x\ XOR\ y,\ XOR(x,y)</tex>
|<font color="black">сложение по модулю 2, не равно, ксор, исключающее «или»</font>
|-
!<tex>x \lor y</tex>
|align = center|<tex>x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),</tex> ''<tex>x </tex><font color="black">ИЛИ </font><tex>y, </tex><font color="black"> ИЛИ</font><tex>(x, y)''</tex> |<font color="black">2ИЛИ, дизъюнкция</font>
|-
!<tex>x \downarrow y</tex>
|align = center|<tex>x\ NOR\ y,\ NOR(x,y)</tex> ''<tex>x </tex><font color="black">ИЛИ-НЕ </font> <tex>y, </tex> <font color="black">ИЛИ-НЕ</font><tex>(x, y)''</tex> |<font color="black">НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса</font>
|-
!<tex>x = y</tex>
|align = center|<tex>x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y</tex>
|<font color="black">равенство, эквивалентность</font>
|-
!<tex>\neg y</tex>
|align = center|<tex>NOT2(x, y),\ y',\ \bar{y},</tex> ''<font color="black">НЕ2</font><tex>(x, y)''</tex> |<font color="black">отрицание (негация, инверсия) второго операнда</font>
|-
!<tex>x \leftarrow y</tex>
|align = center|<tex>x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)</tex>
|<font color="black">больше или равно, обратная импликация (от второго аргумента к первому)</font>
|-
!<tex>\neg x</tex>
|align = center|<tex>NOT1(x,y),\ x',\ \bar{x},</tex> ''<font color="black">НЕ1</font><tex>(x, y)''</tex> |<font color="black">отрицание (негация, инверсия) первого операнда</font>
|-
!<tex>x \rightarrow y</tex>
|align = center|<tex>x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)</tex>
|<font color="black">меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)</font>
|-
!<tex>x \triangledown y</tex>
|align = center|<tex>x \mid y,\ x\ NAND\ y,\ NAND(x,y),</tex> ''<tex>x </tex> <font color="black">И-НЕ </font><tex>y, </tex> <font color="black">И-НЕ</font><tex>(x, y)''</tex> |<font color="black">НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера</font>
|-
!<tex>1</tex>
|
|<font color="black">тождественная единица, тождественная истина, тождественное "ДА", тавтология</font>
|}
</center>
=== Тернарные функции ===
При <tex>n = 3</tex> число булевых функций равно <tex>{2^2}^3 = 2^8 = 256</tex>. Некоторые из них определены в следующей таблице:
<center>{| class="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10" border|+!colspan=1"14"|Таблица истинности некоторых тернарных функций |-align="center"
!class="dark" style="font-weight:normal"| <tex>x</tex>
!class="dark" style="font-weight:normal"| <tex>y</tex>
!style="font-weight:normal"| <tex>max(x,y,z)</tex>
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
|1||1||0||1 ||0||1||0||0||0||0 ||0
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
|0||1||1||1 ||0||0||1||0||0||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
|0||1||1||1 ||0||0||1||0||1||0 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
|0||0||1||1 ||0||0||0||1||0||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 0</font>
|0||0||1||1 ||0||0||0||1||1||1 ||1
|- align="center"
!class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font> !class="shadow" style="font-weight:normal" | <font color="black"> 1</font>
|0||0||0||0 ||1||1||1||1||1||1 ||1
|}
</center>
Названия булевых функций трех переменных:
<center>{| class="standardwikitable" align="center" style="color: blue; background-color:#ffffcc;" bordercellpadding=1"10"|+ |-align="center"
!Обозначения
!Другие обозначения
!<tex>x \downarrow y \downarrow z</tex>
|align = center|<tex>\downarrow (x,y,z) = Webb_2 (x,y,z)</tex>
|<font color="black"> 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса</font>
|-
!<tex>\neg (\geq 2(x,y,z))</tex>
|
|<font color="black">Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией</font>
|-
!<tex>x \not = y \not = z</tex>
|align = center|<tex>[\not =(x,y,z)] = NE(x,y,z)</tex>
|<font color="black">Неравенство</font>
|-
!<tex>x \mid y \mid z</tex>
|align = center|<tex>\mid(x,y,z)</tex>
|<font color="black">3-И-НЕ, штрих Шеффера</font>
|-
!<tex>x \land y \land z</tex>
|align = center|<tex>\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z)= <br/> (x</tex> ''<font color= (x "black"> И </font><tex> y </tex> <font color="black"> И </font><tex> z) = </tex> <font color="black">И</font><tex>(x,y,z)''</tex> |<font color="black">3-И, минимум</font>
|-
!<tex>x=y=z</tex>
|align = center|<tex>[=(x,y,z)] = EQV(x,y,z)</tex>
|<font color="black">Равенство</font>
|-
!<tex>x \oplus y \oplus z</tex>
|align = center|<tex>x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)</tex>
|<font color="black">Тернарное сложение по модулю 2</font>
|-
!<tex>\geq 2(x,y,z)</tex>
|align = center|''<tex>(x </tex> <font color="black">И </font> <tex>y) </tex><font color="black">ИЛИ </font><tex>(y </tex><font color="black"> И </font><tex> z) </tex><font color="black"> ИЛИ </font> <tex>(z </tex><font color="black">И </font><tex> x)''</tex> |<font color="black">переключатель по большинству, 3-ППБ, мажоритарный клапан</font>
|-
!<tex>f_1</tex>
|
|<font color="black">Разряд займа при тернарном вычитании</font>
|-
!<tex>f_2</tex>
|
|<font color="black">Разряд переноса при тернарном сложении</font>
|-
!<tex>x+y+z</tex>
|align = center|<tex>+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) =(x </tex> ''(x <font color="black">ИЛИ </font><tex> y </tex><font color="black"> ИЛИ </font><tex> z) = </tex><font color="black"> ИЛИ</font><tex>(x,y,z)''</tex> |<font color="black">3-ИЛИ, максимум</font>
|}
