5.10. Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0,0,0), (0,0,1), (0,1,0), (0,1,1),
(1,0,0), (1,0,1), (1,1,0), (1,1,1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Примеры.
1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце - значение формулы. В результате получим таблицу:
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.
2. Таблица истинности для формулы :
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.
3. Таблица истинности для формулы :
Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.
www.examen.ru
Как построить таблицу истинности | Сделай все сам
Для всякого логичного выражения дозволено возвести таблицу истинности . Эта таблица наглядно показывает, при каких значениях логических переменных выражение обращается в единицу либо является правдивым. С подмогой составления таблиц истинности дозволено подтвердить равенство (либо неравенство) 2-х трудных логических выражений.
Инструкция
1. Посчитайте число переменных в выражении. Для n логических переменных потребуется 2^n строк таблицы истинности , не считая строки с заголовками. После этого посчитайте число логических операций в выражении. Столбцов в таблице будет столько же, сколько операций плюс n столбцов для переменных.Пускай дано выражение с тремя переменными, записанное на рисунке. Переменных три, следственно строк понадобится 8. Число операций – 3, следственно число столбцов с учетом переменных равно 6. Начертите таблицу и заполните ее заголовок.
2. Сейчас заполните столбцы, надписанные наименованиями переменными, всеми допустимыми вариантами переменных. Дабы не пропустить ни одного варианта, комфортно представить для себя эти последовательности нулей и единиц в виде двоичных чисел от 0 до 2^n. Для 3 переменных это двоичные числа от 0 до 8 либо от 000 до 111 в двоичной системе счисления.
3. Начинать заполнять таблицу истинности особенно комфортно с заполнения итогов отрицания переменных, от того что здесь не требуется делать каких-то трудных умозаключений. В нашем случае легко заполнить столбец отрицания переменной B.
4. После этого подставляйте ступенчато значения переменных в логические операции, указанные в заголовках столбцов, и записывайте в соответствующие ячейки таблицы, ступенчато заполняя таблицу .
Представление «Таблица истинности » узко связано с логическими функциями, в этих функциях переменные могут принимать только логические значения – 0 и 1. Логические функции могут быть заданы с подмогой таблиц истинности , при этом таблица состоит из доводов функции и её значений при этих доводах. При построении таблиц истинности нужно рассматривать порядок выполнения логических операций.
Инструкция
1. Из курса алгебры логик знамениты основные операции над логическими выражениями, порядок их выполнения дальнейший:1. инверсия;2. конъюнкция;3. дизъюнкция;4. импликация;5. эквивалентность.Последовательность операций дозволено менять с подмогой скобок.
2. Таблица истинности для трудного выражения строится по дальнейшему алгорифму:1. Определяется число строк по формулеколичество строк = 2^n + строка для заголовка, где n – число примитивных высказываний,2. Определяется число столбцов по формулеколичество столбцов = число переменных + число логических операций,3. Строится таблица и заполняется итогами операций в вышеуказанной последовательности, при этом применяется таблица истинности примитивных логических операций.
3. К примеру, возьмём такое выражениеD = ¬ А & (B U C).1. В выражении присутствуют высказывания A, B и C, таким образом, n = 3, соответственноколичество строк = 92. Промежуточные итоги:• ¬ А – инверсия, обозначим её буквой E• B U C – дизъюнкция, обозначим её буквой F• D = ¬ А & (B U C) = E & F – конъюнкция3. Таким образом, таблица истинности примет вид, показанный на рисунке.
Видео по теме
jprosto.ru
Построение и анализ таблиц истинности логических выражений / Задания / Информатика :: Бингоскул
Построение и анализ таблиц истинности логических выражений
За правильное выполненное задание получишь 1 балл. На решение отводится примерно 3 минуты.
Для выполнения задания 2 по информатике необходимо знать:
Обозначения логических операций
\lnot A, не A — отрицание, инверсия
A \land B, A и B — логическое умножение, конъюнкция
A \lor B, A или B — логическое сложение, дизъюнкция
A \to B -импликация, следование
A \equiv B — эквивалентность, равносильность
| Приоритет | Операция | Обозначение | |
| 1. Высший | НЕ | NOT | ¬,¯ |
| 2. Высокий | И | AND | &,*,Λ |
| 3. Средний | ИЛИ | OR | V, + |
| 4. Низкий | Следование | IMP | → |
| 5. Низший | Эквивалентность | EQU | ≡,↔ |
| A | B | ¬A | A Λ B | A V B | A → B | A ≡ B |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
bingoschool.ru
Первый способ построения таблицы истинности
Формула содержит 3 различные переменные А, В, С. Составим таблицу всевозможных значений этих переменных. Их будет 8 (определяется как количество сочетаний из 2 (1 или 0, истина или ложь) по 3 (3 переменных А, В, С)), то есть 23=8.
А | В | С | СВ | (СВ)В | АВ | ((СВ)В) (АВ) | ((СВ)В) (АВ)В |
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 |
Ответ: получилась тождественно-истинная формула.
4. Построение логических выражений по заданной таблице истинности
Задание. Дана таблица истинности. Построить логическое (булево) выражение для
А
В
С
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1 0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
Правила построения логического выражения:
Первый способ.
1.
Для каждой строки таблицы истинности
2. Объединить все минтермы операцией дизъюнкцией, что даст стандартную сумму произведений для заданной таблицы истинности.
Все вышесказанное можно продемонстрировать следующим образом:
А
В
С
F
минтермы
0
0
0
0
0
0
1
1
А В С
0
1
0
1
А В С
0
1
1
0
1
0
0
0
1
0
1
1
А В С
1
1
0
0
1
1
1
0
Объединяя термы получим следующее логическое выражение дляF:
Вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю.
Таким образом, мы построили логическое выражение по таблице истинности. В данном случае оно называется стандартной суммой произведений (канонической суммой минтермов).
Полученное таким образом выражение можно упростить, пользуясь законами алгебры логики.
Второй способ.
1. Выделить в таблице истинности все наборы переменных, на которых функция принимает нулевые значения.
2. Для каждого выбранного набора записать элементарные дизъюнкции (например, АВС), причем переменные, имеющие единичные значения в строке, входят в элементарную дизъюнкцию с отрицанием, а переменные со значением 0 – без отрицания.
3. Соединить элементарные дизъюнкции знаком конъюнкции.
Все вышесказанное можно продемонстрировать следующим образом:
А
В
С
F
Элементарные дизъюнкции
0
0
0
0
АВС
0
0
1
1
0
1
0
1
0
1
1
0
А ВС
1
0
0
0
АВС
1
0
1
1
1
1
0
0
А ВС
1
1
1
0
А ВС
Объединяя элементарные дизъюнкции операцией конъюнкцией, получим следующее логическое выражение для F:
Таким образом, мы построили логическое выражение по таблице истинности вторым способом. Его можно упростить, пользуясь законами алгебры логики.
Замечание. В рассмотренном примере построение логического выражения первым способом рациональнее, так как количество термов три. Во втором способе количество элементарных дизъюнкций – 5, что, возможно, усложнит упрощение логического выражения.
studfiles.net
1.8.3. Построение таблиц истинности
Пример 1.8.3-1.Получить таблицу истинности функцииF2, заданной аналитически:
Решение
Для построения таблиц истинности необходимо представить функцию в совершенной форме (СДНФ или СКНФ).
Приведем функцию F2 к совершенной дизъюнктивной форме:
Упростим вторую скобку
2)
Применим правило расширения, чтобы получить СДНФ. УмножимX1X2 наи получим:
Эта функция является СДНФи принимает значение, равное1,на наборах:
000 — 0
111 — 7 = 1, а на остальных наборах значение равное0.
110 — 6
Тогда таблица истинности будет выглядеть следующим образом:
X1 | X2 | X3 | F2 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
1.8.4. Контрольные вопросы по теме «Типовые задачи по преобразованию логических функций»
Назовите типы задач по преобразованию логических функций
Что означает упростить логическую функцию?
Как определяется тождественность логических функций?
Как производится упрощение (минимизация) логических функций?
В какой форме должна быть представлена логическая функция для построения таблиц истинности?
Какое правило следует использовать для представления логической функции в совершенной форме?
Можно ли построить таблицу истинности логической функции, если известны наборы, на которых эта функция принимает одно значение?
1.8.5. Тестовые задания по теме «Типовые задачи по преобразованию логических функций»
Таблица истинности логической функции F=A&
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |||
1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | |||
1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Таблица истинности логической функции F= &B
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |||
1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | |||
1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
Таблица истинности логической функции F= +B
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |||
1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |||
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Таблица истинности логической функции F= A+
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |||
1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | |||
1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
Таблица истинности логической функции F=+
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |||
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | |||
1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | |||
1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Таблица истинности логической функции F=&
1) 2) 3) 4)
A | B | F | A | B | F | A | B | F | A | B | F | |||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | |||
1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | |||
1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Для построения таблиц истинности логическая функция должна быть представлена
в совершенной дизъюнктивной нормальной форме или в совершенной конъюнктивной нормальной форме
в дизъюнктивной нормальной форме или в конъюнктивной нормальной форме
в нормальной форме
Логические функции F1 и F2
являются:
1) нетождественными
2) тождественным
Логические функции F1 и F2
являются:
нетождественными
тождественными
Логическая функция описывается набором аргументов
F=0на наборах1, 2, 3, 4
F=1на наборах0, 5, 7
F=1на наборах0, 6, 7
Какая из предложенных функций является Минимальной формой записи логической функцииF=0, заданной на наборах 0, 1, 2, 3, 4, 6
Логические функции F1 и F2
являются
нетождественными
тождественными
Логическая функция равна
0
1
3
На каких наборах Логическая функция примет значение0 на наборах
0,1, 2, 3, 4,6
1, 3, 4
0, 5, 6, 7
Логические функции являются тождественными
Логические функции являются тождественными
Упростить приведенную ниже схему
Правильным является вариант
Упростить приведенную ниже схему
Правильным является вариант
Упростить приведенную ниже схему
Правильным является вариант
studfiles.net
Составление таблицы истинности
Чтобы проверить сложное суждение с помощью таблицы истинности, необходимо грамотно её составить.
Например, нужно проверить суждение: «Если пойдёт дождь, то дорога будет мокрая».
1. Определим все простые суждения, составляющие данное сложное высказывание и узнаем количество переменных n:
а– пойдёт дождь;b– дорога будет мокрая
Получилось две переменных (а, b), соединённых союзом «если, то»
2. Количество строк (k) в таблице определяется по формуле:k = 2n, гдеn– количество переменных (то есть количество простых суждений, составляющих сложное).
В данном примере k = 22 = 4 Значит будет четыре строчки в таблице.
3. Количество столбцов в таблице будет зависеть от количества операций (логических связок) в сложном суждении.
Сначала в первых столбцах распределяются все возможные значения истины и лжи для переменных.
В данном примере две переменные, следовательно, четыре строки.
В самом правом столбце (b) чередуют «и» и «л» по одному, начиная всегда с «истины»Во втором справа столбце (а) чередуют подряд два значения «и» и два значения «л», начиная всегда с «истины».
а | b |
и | и |
и | л |
л | и |
л | л |
Затем направо выписывают логические формы всех сложных суждений, входящих в рассматриваемое суждение. В данном примере указана одна логическая связка «если, то» – импликация.
а | b | a → b |
и | и | |
и | л | |
л | и | |
л | л |
Осталось определить значения истинности для импликации. Сложное суждение, соединённое импликацией, ложно только в одном случае: если основание (первое суждение) истинно, а следствие (второе суждение) ложно.
а | b | a → b |
и | и | и |
и | л | л |
л | и | и |
л | л | и |
1. Дождь пошёл, дорога мокрая. а– истина;b– истина. Следовательно, если а, тоb(a → b)– истина
2. Дождь пошёл, но дорога не стала мокрая. а– истина;b– ложь. Следовательно, если а, тоb(a → b)– ложно. Невозможно, чтобы причина была, а следствие не наступило.
3. Дождь не пошёл, но дорога мокрая а– ложь;b– истина. Следовательно,a → b – истина. Дорога может быть мокрой и по другой причине.
4. Дождь не пошёл и дорога не намокла. а– ложь;b– ложь. Следовательно,a → b – истина.
Если сложное суждение составлено из трёх простых, то есть состоит из трёх переменных (а,b,c), то таблица истинности, включающая все возможные комбинации истинности или ложности её переменных, будет состоять из 23 = 8 строк.
Алгоритм распределения значений «и» и «л» для трёх переменных таков:
а | b | с | Начинаем распределять значения с крайнего правого столбца (с) и распределяем значения «и» и «л» попеременно, начиная с «истины». Затем распределяем значения во втором столбце справа (b), распределяем значения «и» и «л», чередуя подряд по два значения «и», затем по два значения «л»; затем опять два значения «и» и два значения «л». В крайнем левом столбце (а) чередуем «и» и «л», чередуя подряд сначала четыре значения «и» и затем четыре значения «л» | |
и | и | и | ||
и | и | л | ||
и | л | и | ||
и | л | л | ||
л | и | и | ||
л | и | л | ||
л | л | и | ||
л | л | л |
Упражнения:
1. Запишите высказывание в виде логической формы, используя логические связки: «Если ты сможешь доказать мне свои добрые намерения, то я поверю тебе или же мне придётся вызвать полицию и обвинить тебя в лжесвидетельстве» (Г. Каттнер. Источник миров).
Выпишем все простые суждения, входящие в состав сложного высказывания:
а–ты сможешь доказать мне свои добрые намерения
b–я поверю тебе
с–мне придётся вызвать полицию
d–(мне придётся) обвинить тебя в лжесвидетельствовании.
Определим связки между элементами: если а, то b или с и d
(a → b) ˅ (c ˄ d)
studfiles.net
Как составить таблицу истинности для сложного логического выражения
Сегодня мы постараемся объяснить, как составить таблицу истинности для логического выражения. Обратите внимание на то, что булева алгебра встречается, по меньшей мере, в трех заданиях единого государственного экзамена. Если вы прочитаете данную статью, то, наверняка, получите больше баллов на экзамене по информатике.
Операции
Перед тем как составлять таблицу истинности, предлагаем познакомиться с операциями булевой алгебры.
Начнем наше знакомство с функцией отрицания. Ее также называют инверсией. Приведем такой пример: выражение «я сегодня иду в кино». Применяем к нему инверсию, в результате имеем: «я сегодня НЕ иду в кино».
Теперь поговорим о функциях умножения и сложения, в булевой алгебре они имеют названия – конъюнкция и дизъюнкция соответственно. Предположим, нам говорят: «ты пойдешь в кино, если выучишь уроки и вынесешь мусор». В данном предложении союз «И» выполняет функцию конъюнкции, а «ЕСЛИ» – дизъюнкции.
Логическое следствие – это еще одна сложная операция логики, которая содержит в себе два выражения: условие и следствие. Если интерпретировать на русский язык, то предложение строится примерно следующим образом: «если я успею выучить литературу, то пойду в кино». Часть предложения до запятой – условие, а после запятой – следствие.
Теперь коротко о функции эквивалентности или равнозначности. Провести параллель с русским языком в данном случае довольно сложно. Для равнозначности стоит запомнить, что если два входных выражения являются либо ложными, либо истинными, то результат положительный, то есть равен единице.
Алгоритм
Сейчас мы поговорим о том, как составить таблицу истинности по информатике, а точнее, обсудим алгоритм наших действий.
Для составления таблицы, в первую очередь необходимо определиться с количеством ячеек, столбцов и строк. Будем все делать поэтапно.
- Определяем количество строк. Для этого необходимо подсчитать, сколько переменных входит в состав выражения, и возвести двойку в это число. Например, как составить таблицу истинности, а точнее узнать количество строк для выражения с тремя переменными? Два возводим в третью степень и получаем восемь. Без учета шапки, нам понадобится восемь строк.
- Для того чтобы определить количество столбцов, нам необходимо подсчитать и пронумеровать операции в данном выражении. Например, в выражении неА*С+В всего три операции. Первая – отрицание, вторая – умножение, третья – сложение. Значит для заполнения значений операций нам нужно три колонки. Но, стоит учитывать и то, что наше выражение состоит из трех переменных, а нам необходимо заполнить их возможные комбинации, добавляем еще три колонки. Итого получается 6.
- Далее переходим к перечислению возможных комбинаций переменных и заполнению таблицы. Обязательно учитывайте приоритет операций.
Первый пример (три переменных)
Предлагаем вам решить следующую задачу: вычислите, сколько комбинаций удовлетворяют условию F=1 выражения: (неА+В)*неС+А. А сейчас о том, как составить таблицу истинности для решения задачи. Прибегаем к помощи составленного алгоритма действий.
- Количество строк=9 (восемь комбинаций переменных + одна строчка – шапка таблицы).
- Приоритет функций: 1- инверсия, 2 – сложение в скобках, 3 – инверсия С, 4 – умножение, 5 – сложение.
- Количество столбцов = 8.
- Составление таблицы и заполнение.
Выражение А | Выражение В | Выражение С | Операция №1 | Операция №2 | Операция №3 | Операция №4 | Операция №5 |
— | — | — | + | + | + | + | И |
— | — | + | + | + | — | — | Л |
— | + | — | + | + | + | + | И |
— | + | + | + | + | — | — | Л |
+ | — | — | — | — | + | — | И |
+ | — | + | — | — | — | — | И |
+ | + | — | — | — | + | — | И |
+ | + | + | — | — | — | — | И |
- Нахождение ответа на вопрос.
- Запись ответа. Ответ:6. Обратите внимание на то, что в условии задания спрашивается сколько комбинаций удовлетворяют, но не просится их перечислять.
Второй пример (4 переменных)
Предлагаем вам рассмотреть вопрос: как составить таблицу истинности для формулы: А*В*неС+D? Какое количество комбинаций соответствует: F=0.
Действуем по тому же алгоритму. Количество строк в нашем случае увеличивается до 17, а столбцов – до 8. Приоритет операций:- А*В;
- неС;
- перемножение результатов первой и второй операции;
- сложение результат третьей операции и значения переменной D.
Предлагаем вам самостоятельно попробовать составить и заполнить таблицу, а затем свериться с результатами в данном разделе статьи.
Переменная А | Переменная В | Переменная С | Переменная D | Умножение (1) | Инверсия (2) | Умножение (3) | Сложение (4) |
— | — | — | — | — | + | — | — |
— | — | — | + | — | + | — | + |
— | — | + | — | — | — | — | — |
— | — | + | + | — | — | — | + |
— | + | — | — | — | + | — | — |
— | + | — | + | — | + | — | + |
— | + | + | — | — | — | — | — |
— | + | + | + | — | — | — | + |
+ | — | — | — | — | + | — | — |
+ | — | — | + | — | + | — | + |
+ | — | + | — | — | — | — | — |
+ | — | + | + | — | — | — | + |
+ | + | — | — | + | + | + | + |
+ | + | — | + | + | + | + | + |
+ | + | + | — | + | — | — | — |
+ | + | + | + | + | — | — | + |
Из полученной таблицы мы делаем вывод: данному условию удовлетворяет 7 различных комбинаций переменных.
fb.ru