«Составление таблиц истиности логических функций» теоретическая часть
Пусть множество Х состоит из двух элементов 0 и 1. Тогда совокупность координат некоторого фиксированного вектора (x1, …,xn)X называется двоичным набором.
Каждому двоичному набору можно поставить в соответствие некоторый номер, равный двоичному числу, соответствующему данному набору.
Например,
(0,1,1) = 021110 = 022 + 121 + 120 + 2 + 1 = 3
(0,0,1,1) = 03021110 = 023 + 022 + 121 + 120 += 0 +0 + 2 + 1 = 3
Чтобы восстановить набор по номеру, нужно знать количество аргументов.
Логическая переменная – это переменная, которая может принимать только два значения – ИСТИНА или ЛОЖЬ (TRUE/FALSE, 1/0).
Функция алгебры логики (булева функция, ФАЛ) – F(x1, …,xn) – это функция у которой все аргументы логические переменные и сама функция принимает только логические значения.
Количество всевозможных, различных двоичных наборов длиной n = 2n.
Например.
n = 3 2n = 23 = 8.
Для функции, зависящей от 3 переменных, аргументы имеют 8 различных двоичных наборов. Эти наборы соответствуют трехразрядным двоичным числам от 0 до 7 (0002 – 1112).
n = 4 2n = 24 = 16.
Для функции, зависящей от 4 переменных, аргументы имеют 16 различных двоичных наборов. Эти наборы соответствуют четырехразрядным двоичным числам от 0 до 15 (00002 – 11112).
ФАЛ можно представить табличным и графическим способом.
Любую ФАЛ можно представить таблицей, имеющей 2n строк. Такая таблица называется таблицей истинности ФАЛ.
В левой части таблицы перечисляются всевозможные двоичные наборы значений аргументов, а в правой части – значения некоторой булевой функции.
Функции алгебры логики.
Каждая функция имеет свою таблицу истинности. При одних наборах аргументов значение ее равно1, т.е. истинно, а при других равно 0, т.е. ложно. Ниже приведена таблица, включающая таблицы истинности логических функций, их название и обозначение.
|
|
Функция |
|
|
Функция | ||||||||||
|
Х1 |
Х2 |
Х1Х2 |
х1 х2 логическое «ИЛИ», дизъюнкция, сумма, OR Функция принимает значение ИСТИНА, если хотя бы один из аргументов имеет значение ИСТИНА |
|
Х1 |
Х2 |
Х1 Х2 |
х1 ↓ х2 логическое «ИЛИ-НЕ», стрелка Пирса, функция Вебба Функция принимает значение ИСТИНА, если оба аргументов имеют значение ЛОЖЬ | ||||||
|
0 |
0 |
0 |
|
0 |
0 |
1 | ||||||||
|
0 |
1 |
1 |
|
0 |
1 |
0 | ||||||||
|
1 |
0 |
1 |
|
1 |
0 |
0 | ||||||||
|
1 |
1 |
1 |
|
1 |
1 |
0 | ||||||||
|
Х1 |
Х2 |
Х1Х2 |
Х1Х2 логическое «И», конъюнкция, AND Функция принимает значение ИСТИНА, если оба аргумента имеют значение ИСТИНА |
|
Х1 |
Х2 |
Х1 Х2 |
Х1 Х2 логическое «И-НЕ», Штрих Шеффера Функция принимает значение ЛОЖЬ, если оба аргумента имеют значение ИСТИНА | ||||||
|
0 |
0 |
0 |
|
0 |
0 |
1 | ||||||||
|
0 |
1 |
0 |
|
0 |
1 |
1 | ||||||||
|
1 |
0 |
0 |
|
1 |
0 |
1 | ||||||||
|
1 |
1 |
1 |
|
1 |
1 |
0 | ||||||||
|
Х1 |
Х2 |
Х1Х2 |
Х1Х2 Сложение по модулю 2, неравнозначность Функция принимает значение ИСТИНА, если оба аргумента имеют разные значения |
|
Х1 |
Х2 |
Х1Х2 |
Х1Х2 Эквивалентность, равнозначность, тождество Функция принимает значение ИСТИНА, если оба аргумента имеют одинаковые значения | ||||||
|
0 |
0 |
0 |
|
0 |
0 |
1 | ||||||||
|
0 |
1 |
1 |
|
0 |
1 |
0 | ||||||||
|
1 |
0 |
1 |
|
1 |
0 |
0 | ||||||||
|
1 |
1 |
0 |
|
1 |
1 |
1 | ||||||||
|
Х1 |
Х2 |
Х1Х2 |
Х1Х2 Импликация Функция принимает значение ЛОЖЬ, если из ИСТИНЫ следует ЛОЖЬ |
|
|
Х |
|
Логическое НЕ, отрицание, NOT | ||||||
|
0 |
0 |
1 |
|
|
0 |
1 | ||||||||
|
0 |
1 |
1 |
|
|
1 |
0 | ||||||||
|
1 |
0 |
0 |
|
|
|
|
| |||||||
|
1 |
1 |
1 |
|
|
|
|
| |||||||
Условные приоритеты булевых функций
|
1 |
( ) |
|
2 |
Отрицание |
|
3 |
|
|
4 |
|
В пределах одного приоритета операции в выражении выполняются слева направо.
Таблица 3. Таблица истинности логических функций
|
Х1 |
Х2 |
Х1Х2 |
Х1 Х2 |
Х1Х2 |
Х1 Х2 |
Х1Х2 |
Х1Х2 |
Х1Х2 |
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
Например:
Дана
функция 
Составить таблицу истинности функции трех переменных F(x, y, z).
Решение.
Расставим порядок выполнения действий, соблюдая приоритеты.
|
|
|
|
3 |
1 |
5 |
6 2 |
4 |
7 |
|
|
| |||||||||
Выполним операции согласно порядку от 1 до 6. Результат выполнения каждой логической операции соответствует ее значению в таблице истинности для данного набора аргументов (таблица 3).
Составим таблицу истинности заданной функции. Число переменных равно3 значит в таблице 8 строк (n – 3 2n = 23 = 8).
Таблица 4.
|
№ набора |
X |
Y |
Z |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
| ||||
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
4 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
5 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
6 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
7 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
В столбце 7 получены значения заданной функции на каждом из двоичных наборов.