Построение таблиц истинности и логических функций
Таблица истинности – таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение – составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
1. Логическое умножение или конъюнкция:
Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложенное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
2. Логическое сложение или дизъюнкция:
Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны.
Обозначение: F = A + B.
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
3. Логическое отрицание или инверсия:
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
|
|
|
Таблица истинности для инверсии
| A | неА |
| 1 | 0 |
| 0 | 1 |
4. Логическое следование или импликация:
Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5. Логическая равнозначность или эквивалентность:
Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Порядок выполнения логических операций в сложном логическом выражении представлены в пункте 3.2.
Алгоритм построения таблиц истинности для сложных выражений:
1. Определить количество строк:
количество строк = 2n + строка для заголовка,
n - количество простых высказываний.
|
|
|
2. Определить количество столбцов:
количество столбцов = количество переменных + количество логических операций;
- определить количество переменных (простых выражений);
- определить количество логических операций и последовательность их выполнения.
3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Пример: Составить таблицу истинности логического выражения:
D = А & (B Ú C).
Решение: Ù
1. Определить количество строк:
на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 23 +1 = 9.
2. Определить количество столбцов:
- простые выражения (переменные): А, В, С;
-промежуточные результаты (логические операции):
А- инверсия (обозначим через E);
B Ú C- операция дизъюнкции (обозначим через F);
а также искомое окончательное значение арифметического выражения:
D = А & (B Ú C). т.е. D = E & F - это операция конъюнкции.
3. Заполнить столбцы с учетом таблиц истинности логических операций.
| B | C | E | F | E & F | B |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 |
Построение логической функции по ее таблице истинности:
|
|
|
Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):
| X | Y | Z |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Составить логическую функцию для заданной таблицы истинности.
Правила построения логической функции по ее таблице истинности:
1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.
Решение.
1. В первой и третьей строках таблицы истинности значение функции равно 1.
2. Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).
3. Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).
4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию: Z (X, Y)=(X& Y) V (X & Y).
|
|
|
Пример. Для формулы A/\(B\/ B/\C) постройте таблицу истинности.
Количество логических переменных 3, следовательно, количество строк - 23 = 8. Количество логических операций в формуле 5, количество логических переменных 3, следовательно, количество столбцов - 3 + 5 = 8.
| А | В | С | -В | -С | -ВÙ-С | ВÚ-ВÙ-С | АÙ(ВÚ-ВÙ-С) |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Пример . Определите истинность логического выражения F(А,В) = (А\/ В)/\(А\/В) .
1. В выражении две переменные А и В (n=2).
2. mстрок=2n, m=22=4 строки.
3. В формуле 5 логических операций.
4. Расставляем порядок действий.
1) А\/ В; 2) А; 3) В; 4) А\/В; 5) (А\/ В)/\(А\/В).
5. Кстолбцов=n+5=2+5=7 столбцов.
| А | В | А\/ В | А | В | А\/В | F |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.
Пример. Построите таблицу истинности для логического выражения
F = (A\/ B)/\С.
1. В данной функции три логические переменные – А, В, С.
2. Количество строк таблицы = 23 =8.
3. В формуле 3 логические операции.
4. Расставляем порядок действий: 1. А\/ В; 2. С; 3. (AVB)/\С.
5. Количество столбцов таблицы = 3 + 3 = 6.
| А | В | С | A\/B | С | (A\/B) /\ С |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Пример. Определите истинность формулы: F =((С\/В)=>В)/\(А /\В) =>В. Построим таблицу истинности этой формулы.
| А | В | С | СÚВ | (СÚВ)®В | АÙВ | ((СÚВ)®ВÙ(АÙВ) | F |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ответ: формула является тождественно истинной.
Пример. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
| X | Y | Z | F |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
Какое выражение соответствует F?
1. X/\Y/\Z;
2. X\/Y\/Z;
3. X\/Y\/Z;
4. X\/Y\/Z.
Решение (вариант 1, через таблицы истинности):
Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:
| X | Y | Z | F | X | Y | Z | X/\Y/\Z | X\/Y\/Z | X\/Y\/Z | X\/Y\/Z |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/Z. Следовательно, правильный ответ – 3.
Решение (вариант 2):
Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.
Рассмотрим данный конкретный пример:
1) первое заданное выражение X/\Y/\Z= 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;
2) второе заданное выражение X\/Y\/Z= 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;
3) третье выражение X\/Y\/Z соответствует F при всех предложенных комбинациях X, Y и Z;
4) четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы. Ответ 3.
Пример. Составить таблицу истинности для логических функции
.
1. Определить порядок действий: 
.
2. Определить размерность таблицы истинности.
«Шапка» таблицы содержит две строки-номера действий и логические операции действий. Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).
1. Количество строк в таблице равно двойке в степени, равной количеству логических переменных – в случае двух переменных получается 4 строки.
| 1 | 2 | ||
| А | В | 1  В
| |
2. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.
| 1 | ||
| А | В | |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 2 | ||
| А | В | 1 В
| |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
3. Сформулировать ответ. В последнем столбце один «0», соответствующий А, равному «1», и В, равному «0». Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции Следствие.
Значит данная функция равна логическому следствию переменных А и В: Если А то В. 
.
Пример. Определить порядок действий.
Определить размерность таблицы истинности.
1. «Шапка» таблицы содержит две строки-номера действий и логические операции действий. Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).
2. Количество строк в таблице равно двойке в степени, равной количеству логических переменных – в случае двух переменных получается 4 строки.
3. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.
| аргументы | 1 | 2 | 3 | 4 | 5 | |
| А | В | А&В | 2&3 | 1Ú4 | ||
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 |
4. Сформулировать ответ. В последнем столбце один «1», соответствуют А, равному В, а «0» - А неравному В. Получается, что данная функция истина, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит данная функция равна логическому тождеству А и В: А тождественно В.
Дата добавления: 2019-09-13; просмотров: 1490; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!