Реферат: Преобразование логических выражений

Тема: Преобразование логических выражений.

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,, ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (,, ¬), что еще раз подчеркивает проблему.

Что нужно знать:

условные обозначения логических операций

¬ A, не A (отрицание, инверсия)

A  B, A и B (логическое умножение, конъюнкция)

A  B, A или B (логическое сложение, дизъюнкция)

A → B импликация (следование)

A ↔ B эквиваленция (эквивалентность, равносильность)

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬ A  B или в других обозначениях A → B =

операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

A ↔ B = ¬ A  ¬ B  A  B или в других обозначениях A ↔ B =

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

правила преобразования логических выражений (слайд из презентации «Логика»):


^ Пример задания:
Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X) → (50 > (X+1)·(X+1))

Решение (вариант 1):

это операция импликации между двумя отношениями и

попробуем сначала решить неравенства

,

обозначим эти области на оси X:




на рисунке фиолетовые зоны обозначают область, где истинно выражение , голубая зона – это область, где истинно

вспомним таблицу истинности операции «импликация»:

A

B

A → B

0

0

1

0

1

1

1

0

0

1

1

1

согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена зеленым цветом

поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7

таким образом, верный ответ – 7 .

Возможные проблемы:

в этом примере потребовалось применить знания не только (и не столько) из курса информатики, но и умение решать неравенства

нужно не забыть правила извлечения квадратного корня из обеих частей неравенства (операции с модулями)

Решение (вариант 2, преобразование выражения):

сначала можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:



это значит, что выражение истинно там, где или

дальнейшие действия точно такие же, как и в варианте 1.

Возможные проблемы:

нужно помнить формулу для преобразования импликации
^ Еще пример задания:
Сколько различных решений имеет уравнение

((K  L) → (L  M  N)) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1):

перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1 и L · M · N = 0

из первого уравнения следует, что хотя бы одна из переменных, K или L равна 1 (или обе вместе); поэтому рассмотрим три случая

если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

таким образом, всего получаем 4 + 3 + 3 = 10 решений.

Совет:

лучше начинать с того уравнения, где меньше переменных



Возможные проблемы:

есть риск потерять какие-то решения при переборе вариантов
^ Еще пример задания:
Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М  L)  К) → (¬К  ¬М)  N)

ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

^ Решение (вариант 1, анализ исходного выражения):

запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):



из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных

из таблицы истинности операции «импликация» (см. первую задачу) следует, что это выражение ложно тогда и только тогда, когда одновременно

и

первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили

из второго условия, , при и получаем

таким образом, правильный ответ – 1000.



Возможные проблемы:

переменные однозначно определяются только для ситуаций «сумма = 0» (все равны 0) и «произведение = 1» (все равны 1), в остальных случаях нужно рассматривать разные варианты

не всегда выражение сразу распадается на 2 (или более) отдельных уравнения, каждое из которых однозначно определяет некоторые переменные


Решение (вариант 2, упрощение выражения):

запишем уравнение, используя более простые обозначения операций:



заменим импликацию по формуле :



раскроем инверсию сложного выражения по формуле де Моргана :



упростим выражение :



мы получили уравнение вида «сумма = 0», в нем все слагаемые должны быть равны нулю

поэтому сразу находим

таким образом, правильный ответ – 1000.



Замечание:

этот способ работает всегда и дает более общее решение; в частности, можно легко обнаружить, что уравнение имеет несколько решений (тогда оно не сведется к форме «сумма = 0» или «произведение = 1»)



Возможные проблемы:

нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой
^ Еще пример задания:
Составьте таблицу истинности для логической функции

X = (А ↔ B)  ¬(A → (B  C))

в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления.


Решение (вариант 1):

запишем уравнение, используя более простые обозначения операций:



это выражение с тремя переменными, поэтому в таблице истинности будет 23=8 строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр


А

В

С

X

0

0

0




0

1

1




0

0

1




1

0

1




1

1

1




0

1

0




1

0

0




1

1

0



переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

27 = 000110112 77 = 010011012 120 = 011110002

теперь можно составить таблицу истинности (см. рисунок справа), в которой строки переставлены в сравнении с традиционным порядком1; зеленым фоном выделена двоичная записи числа 27 (биты записываются сверху вниз), синим – запись числа 77 и розовым – запись числа 120:

вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)

заполняем столбцы таблицы:

А

В

С









X

0

0

0

1

0

1

0

1

0

1

1

0

1

1

0

0

0

0

1

1

1

1

0

1

1

0

1

0

1

1

0

0

1

1

1

1

1

1

0

1

0

1

0

0

1

1

0

0

1

0

0

0

0

0

1

1

1

1

0

1

1

1

0

1

значение равно 1 только в тех строчках, где А = В

значение равно 1 только в тех строчках, где В = 1 или С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение – это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

результат Х (последний столбец) – это логическая сумма двух столбцов, выделенных фиолетовым фоном

чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 101010112

переводим это число в десятичную систему: 101010112 = 27 + 25 + 23 + 21 + 20 = 171

таким образом, правильный ответ – 171.



Возможные проблемы:

нужно помнить таблицы истинности логических операций

легко запутаться в многочисленных столбцах с однородными данными (нулями и единицами)

Решение (вариант 2, преобразование логической функции):

выполним пп. 1-5 так же, как и в предыдущем способе

запишем уравнение, используя более простые обозначения операций:



раскроем импликацию через операции И, ИЛИ и НЕ ():



раскроем инверсию для выражения по формуле де Моргана:



таким образом, выражение приобретает вид

отсюда сразу видно, что Х = 1 только тогда, когда А = В или (А = 1 и В = С = 0):

А

В

С

X

Примечание

0

0

0

1

А = В

0

1

1

0




0

0

1

1

А = В

1

0

1

0




1

1

1

1

А = В

0

1

0

0




1

0

0

1

А = 1, В = С = 0

1

1

0

1

А = В

чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 101010112

переводим это число в десятичную систему: 101010112 = 27 + 25 + 23 + 21 + 20 = 171

таким образом, правильный ответ – 171.



Возможные проблемы:

нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой



1 Проверьте, что обычно (когда комбинации располагаются по возрастанию соответствующих двоичных чисел), столбец значений аргумента А представляет собой двоичную запись числа 15 = 11112, столбец значений аргумента В – числа 51 = 1100112, столбец значений аргумента С – числа 85 = 101010102.