Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Построение таблиц истинности логических выражений.

Алгебра логики — это раздел математики, изучающий
высказывания, рассматриваемые со стороны их логических
значений (истинности или ложности) и логических операций
над ними.
Логическое высказывание — это любoе повествовательное
пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «ученик десятого класса» и «информатика — интересный предмет«. Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие «интересный предмет«. Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

Предложения типа «в городе A более миллиона жителей«, «у него голубые глаза» не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предложения называются высказывательными формами.

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание «площадь поверхности Индийского океана равна 75 млн кв. км» в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

Употребляемые в обычной речи слова и словосочетания «не»,   «и»,   «или»,  «если… , то»,   «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются   логическими связками.

Bысказывания, образованные из других высказываний с помощью логических связок, называются   составными. Высказывания, не являющиеся составными, называются   элементарными.

Так, например, из элементарных высказываний «Петров — врач«, «Петров — шахматист» при помощи связки «и» можно получить составное высказывание «Петров — врач и шахматист«, понимаемое как «Петров — врач, хорошо играющий в шахматы«.

При помощи связки «или» из этих же высказываний можно получить составное высказывание «Петров — врач или шахматист«, понимаемое в алгебре логики как «Петров или врач, или шахматист, или и врач и шахматист одновременно«. Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Решение заданий.

Задание 1.Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:

Каким выражением может быть F?

  • в последнем столбце в таблице видим одну единицу и два нуля, поэтому это не может быть дизъюнкция, которая даёт ноль только при одном наборе значений переменных; таким образом, варианты 2 и 4 заведомо неверные, нужно сделать выбор между ответами 1 и 3
  • рассматриваем «особую» строчку таблице, в которой функция равна 1;
  • поскольку мы говорим о конъюнкции, переменная  должна входить в неё с инверсией (это выполняется для обоих оставшихся вариантов), а переменная – без инверсии; последнее из этих двух условий верно только для варианта 3. Ответ: 3.

Задание 2.Дан фрагмент таблицы истинности выражения F.

Какое выражение соответствует F?

     Решение:

  • в этом задании среди значений функции только одна единица, как у операции «И», это намекает на то, что нужно искать правильный ответ среди вариантов, содержащих «И», «НЕ» и импликацию (это варианты 1 и 3)
  • действительно, вариант 2 исключён, потому что при 4=1 во второй строке получаем 1, а не 0
  • аналогично, вариант 4 исключён, потому что при 5=1 в первой строке получаем 1, а не 0
  • итак, остаются варианты 1 и 3; вариант 1 не подходит, потому что при 6=0 в третьей строке получаем 0, а не 1
  • проверяем подробно вариант 3, он подходит во всех строчках

Ответ: 3.

Задание 3.Дано ло­ги­че­ское вы­ра­же­ние, за­ви­ся­щее от 5 ло­ги­че­ских пе­ре­мен­ных:               z1 ∧ ¬z2 ∧ ¬z3 ∧ ¬z4 ∧ z5

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний пе­ре­мен­ных, при ко­то­рых вы­ра­же­ние ложно?

1) 1                    2) 2                  3) 31                  4) 32

По­яс­не­ние.

Опе­ра­ция конъ­юнк­ции воз­вра­ща­ет лож­ное зна­че­ние, если хотя бы один из её ар­гу­мен­тов ложен, т.е. су­ще­ству­ет толь­ко один ва­ри­ант, воз­вра­ща­ю­щий ис­ти­ну. Сле­до­ва­тель­но, ис­ко­мое число ва­ри­ан­тов равно 25-1 = 31 (число 2 воз­во­дит­ся в пятую сте­пень, так как всего пе­ре­мен­ных 5 и каж­дая из них может при­ни­мать два зна­че­ния).

Ответ: 31.

Задание 4. Дан фраг­мент таб­ли­цы ис­тин­но­сти вы­ра­же­ния F: 

Каким вы­ра­же­ни­ем может быть F?

1) (x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (x5 ∧ x6)

2) (x1 ∧ x3) ∨ (x3 ∧ x5) ∨ (x5 ∧ x1)

3) (x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2)

4) (x1 ∧ x4) ∨ (x2 ∧ x5) ∨ (x3 ∧ x6)

По­яс­не­ние.

Все пред­став­лен­ные здесь ва­ри­ан­ты от­ве­та — дизъ­юнк­ции трёх конъ­юнк­ций. Все пред­став­лен­ные зна­че­ния F равны нулю. Дизъ­юнк­ция равна нулю тогда и толь­ко тогда, когда все её опе­ран­ды равны нулю.

Рас­смот­ри по­очерёдно все че­ты­ре вы­ра­же­ния.

Пер­вое вы­ра­же­ние. В пер­вой стро­ке таб­ли­цы x1 и x2 равны еди­ни­це, зна­чит x1∧x2=1. Этот ва­ри­ант от­ве­та нам не под­хо­дит.

Вто­рое вы­ра­же­ние. Во вто­рой стро­ке таб­ли­цы x1 и x3 равны еди­ни­це, зна­чит x1∧x3=1. Этот ва­ри­ант от­ве­та нам не под­хо­дит.

Тре­тье вы­ра­же­ние. Про­ве­рим все стро­ки таб­ли­цы.

Про­ве­рим первую стро­ку таб­ли­цы.
(x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = 0 ∨ 0 ∨ 0 = 0 — верно.

Про­ве­рим вто­рую стро­ку таб­ли­цы. (x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = 0 ∨ 0 ∨ 0 = 0 — верно.

Про­ве­рим тре­тью стро­ку таб­ли­цы. (x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = 0 ∨ 0 ∨ 0 = 0 — верно.

Четвёртое вы­ра­же­ние. В тре­тьей стро­ке таб­ли­цы x1 и x4 равны еди­ни­це, зна­чит x1∧x4=1. Этот ва­ри­ант от­ве­та нам не под­хо­дит.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

За­да­ние 5. Для таб­ли­цы ис­тин­но­сти функ­ции F из­вест­ны зна­че­ния толь­ко не­ко­то­рых ячеек: 

Каким вы­ра­же­ни­ем может быть F?

1) x1 ∧ x2 ∧ x3 ∧ x4 ∧ x5 ∧ x6 ∧ ¬x7

2) ¬x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7

4) x1 ∨ x2 ∨ ¬ x3 ∨ ¬x4 ∨ x5 ∨ ¬x6 ∨ x7

По­яс­не­ние.

Про­ана­ли­зи­ру­ем каж­дый ва­ри­ант.

Пер­вый ва­ри­ант не под­хо­дит, по­сколь­ку в пер­вой стро­ке пе­ре­мен­ная x6 = 0, сле­до­ва­тель­но, F долж­но об­ра­щать­ся в нуль, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

Вто­рой ва­ри­ант не под­хо­дит, по­сколь­ку в тре­тьей стро­ке пе­ре­мен­ная ¬ x1 = 1, сле­до­ва­тель­но, F долж­но быть равно 1, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

Тре­тий ва­ри­ант не под­хо­дит, по­сколь­ку во пер­вой стро­ке пе­ре­мен­ная x6 = 0, сле­до­ва­тель­но, F долж­но об­ра­щать­ся в нуль, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

Ответ: 4.

Задание 6. Логическая функция F задаётся выражением (¬z)/\x \/ x/\y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и таблица истинности:

Тогда 1-му столбцу соответствует переменная y, а 2-му столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение: Для начала, преобразуем наше исходное выражение:
(¬z)/\x \/ x/\y = (¬z/\x) (\/ x/\y) = х /\ (¬z \/ y)

Конъюнкция истинна тогда и только тогда, когда истинны оба высказывания. Следовательно переменной х должен соответствовать тот столбец, в котором значение 1 стоит в тех же строках, что и в столбце F.

Таким образом переменной x соответствует 3 столбец.

Дизъюнкция двух высказываний ложна тогда и только тогда, когда ложны оба высказывания.
Дизъюнкция ¬z \/ y в данной строке ложна. Следовательно, у=0, z=1.

Ответ: zyx

Задание 7. Логическая функция F задаётся выражением x /\ ¬y /\ (¬z \/ w).

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна.

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т. д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.

Тогда первому столбцу соответствовала бы переменная y, а второму

столбцу – переменная x. В ответе следовало бы написать: yx.

Решение: x /\¬y /\ (¬z \/ w) Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания. Следовательно переменной х должен соответствовать тот столбец, в котором стоит значение 1.

Таким образом, переменной x соответствует столбец с переменной 3.

Переменной ¬y должен соответствовать тот столбец, в котором стоит значение 0.

Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ y в данной строке будет истинна только если z=0w=1.

Таким образом, переменной ¬z соответствует столбец с переменной 1 (1 столбец), переменной w соответствует столбец с переменной 4 (4 столбец).

Ответ: zyxw

Задание 8. (Демонстрационный вариант ЕГЭ по информатике 2018 года). Логическая функция F задаётся выражением ¬x ∨ y ∨ (¬z ∧ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т. д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Ответ запишите МАЛЕНЬКИМИ ЛАТИНСКИМИ буквами.

  • Для удобства логическое выражение можно переписать в следующем виде:

¬x + y + (¬z * w)

  • Данное логическое уравнение имеет корневой (последней) операцией — дизъюнкцию (логическое сложение). Дизъюнкция бывает ЛОЖНА только в одном случае, когда все слагаемые ложны. Следовательно:

¬x = 0

  y = 0

¬z * w = 0

  • Рассмотрим первое слагаемое и таблицу истинности: ¬x = 0 , значит х = 1 . Во всех строчках нашей таблицы истинности, х д. б. равен 1. Только в первом столбце это правило выполняется.

Вывод: перем.1 — это х

  • Аналогично, делаем вывод, что переменной 4 м. б. только у (т. к. у д. б. всегда равен 0)
  • Остались две переменные, они имеют разные значения только во второй строке таблицы истинности: перем.2=1, а перем.3=0

¬z * w = 0

Следовательно, z — это перем.2, а w — это перем.3

Ответ: xzwy

Top