Анализ таблиц истинности логических выражений
Скачать 2.43 Mb.
|
Ещё пример задания:Р-13. Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A B? Решение: полная таблица истинности каждого выражения с пятью переменными содержит 25 = 32 строки в каждой таблице по 4 единицы и по 28 (= 32 – 4) нуля выражение A B равно нулю тогда и только тогда, когда A = 0 и B = 1 минимальное количество единиц в таблице истинности выражения A B будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно A = 0 и B = 1 по условию A = 0 в 28 строках, и B = 1 в 4 строках, поэтому выражение A B может быть равно нулю не более чем в 4 строках, оставшиеся 32 – 4 = 28 могут быть равны 1 Ответ: 28. Ещё пример задания:Р-12. Дан фрагмент таблицы истинности для выражения F:
Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x1 не совпадает с F. Решение: полная таблица истинности выражения с пятью переменными содержит 25 = 32 строки в приведённой части таблицы в двух строках значение x1 совпадает с F, а в одной – не совпадает во всех оставшихся (неизвестных) 32 – 3 = 29 строках значения x1 и F могут не совпадать всего несовпадающих строк может быть 1 + 29 = 30. Ответ: 30. Ещё пример задания:Р-11. Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:
Каким выражением может быть F? 1) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7 ¬x8 2) x1 x2 x3 ¬x4 ¬x5 ¬x6 ¬x7 ¬x8 3) ¬x1 x2 ¬x3 x4 x5 ¬x6 ¬x7 ¬x8 4) x1 ¬x2 x3 ¬x4 ¬x5 ¬x6 ¬x7 ¬x8 Решение: перепишем выражения в более простой форме, заменив «И» () на умножение и «ИЛИ» () на сложение: 1) 2) 3) 4) в последнем столбце таблицы истинности видим две единицы, откуда сразу следует, что это не может быть цепочка операций «И» (конъюнкций), которая даёт только одну единицу; поэтому ответы 1 и 3 заведомо неверные анализируем первую строку таблицы истинности; мы знаем в ней только два значения - и для того, чтобы в результате в первой строке получить 0, необходимо, чтобы переменная входила в сумму с инверсией (тогда из 1 получится 0!), это условие выполняется для обоих оставшихся вариантов, 2 и 4 кроме того, переменная должна входить в выражение без инверсии (иначе соответствующее слагаемое в первой строке равно 1, и это даст в результате 1); этому условию не удовлетворяет выражение 4; остается один возможный вариант – выражение 2 Ответ: 2. |