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

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



НазваниеТема : Построение таблиц истинности логических выражений
Дата конвертации06.10.2012
Размер301.81 Kb.
ТипДокументы
источник

© К. Поляков, 2009-2010

A9 (базовый уровень, время – 2 мин)


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

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

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

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

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

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

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

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

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

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

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

  • иногда для упрощения выражений полезны формулы де Моргана:

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B

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

  • таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных

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

  • количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

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

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

П

X

Y

Z

F

1

0

0

1

0

0

0

1

1

1

1

0


ример задания:


^ Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

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

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

Решение (основной вариант):

  1. нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных

  2. если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F

  3. перепишем ответы в других обозначениях:
    1) 2) 3) 4)

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

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

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

  7. наконец, четвертое выражение, равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности

  8. таким образом, правильный ответ – 4 ; частичная таблица истинности для всех выражений имеет следующий вид:

X

Y

Z

F









1

0

0

1

0 ×

0 ×

1

1

0

0

0

1





   0 ×

1

1

1

1

0







0

(красный крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).

^ Возможные ловушки и проблемы:

    • серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно перевести их в «удобоваримый» вид;

    • расчет на то, что ученик перепутает значки и (неверный ответ 1)

    • в некоторых случаях заданные выражения-ответы лучше сначала упростить, особенно если они содержат импликацию или инверсию сложных выражений (как упрощать – см. разбор задачи А10)

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

  1. часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности

  2. в этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов

  3. в приведенной задаче в столбце F есть единственный нуль для комбинации

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

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




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

    • метод применим не всегда, то есть, найденная в п. 4 функция может отсутствовать среди ответов

Е

X

Y

Z

F

1

0

0

1

0

0

0

0

1

1

1

0


ще пример задания:


^ Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

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

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  ¬Y  ¬Z 4) X  ¬Y  ¬Z

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

  1. перепишем ответы в других обозначениях:
    1) 2) 3) 4)

  2. в столбце F есть единственная единица для комбинации , простейшая функция, истинная (только) для этого случая, имеет вид , она есть среди приведенных ответов (ответ 3)

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

З

X

Y

Z

F

1

1

1

1

1

1

0

1

1

0

1

1


адачи для тренировки1:


  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  ¬Y  Z 2) X  Y  Z 3) X  Y  ¬Z 4) ¬X  Y  ¬Z


X

Y

Z

F

0

1

0

0

1

1

0

1

1

0

1

0






  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  ¬Z 2) X  Y  ¬Z 3) ¬X  ¬Y  Z 4) X  ¬Y  Z


X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

0






  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) ¬X  ¬Y  ¬Z


X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

1






  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  ¬Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) X  Y  Z


A

B

F

0

0

1

0

1

1

1

0

1

1

1

0






  1. Символом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?

1) A (¬A  ¬B) 2) A  B 3) ¬AB 4) ¬A  ¬B



X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1






  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  (Y  Z) 4) (X  Y)  ¬Z


X

Y

Z

F

0

0

0

1

0

0

1

1

0

1

0

1






  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z


X

Y

Z

F

0

0

0

1

0

0

1

1

0

1

0

1

1




  1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬(X  Y)  Z 2) ¬(X  ¬Y)  Z 3) ¬(X  Y)  Z 4) (X  Y)  Z



  1. С

    X

    Y

    Z

    F

    0

    0

    0

    0

    1

    0

    1

    1

    0

    1

    0

    1


    имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  Y  Z 4) X  Y  ¬Z


A

B

F

0

0

0

0

1

1

1

0

1

1

1

1






  1. Символом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?

1) A (¬(A  ¬B)) 2) A  B 3) ¬AB 4) ¬A  B



  1. С

    X

    Y

    Z

    F

    1

    1

    1

    1

    1

    1

    0

    1

    1

    0

    1

    1

    0
    имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  ¬Y  Z 3) X  Y  Z 4) X  Y  ¬Z



  1. С

    X

    Y

    Z

    F

    1

    0

    0

    0

    0

    0

    0

    1

    1

    0

    1

    1


    имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  Z 2) X  Y  ¬Z 3) ¬X  ¬Y  Z 4) X  ¬Y ¬ Z



  1. С

    X

    Y

    Z

    F

    0

    1

    1

    1

    0

    1

    0

    0

    1

    0

    1

    0


    имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  ¬Z 2) ¬X  Y  Z 3) X  ¬Y  ¬Z 4) ¬X  ¬Y  Z



  1. С

    X

    Y

    Z

    F

    1

    0

    0

    0

    0

    0

    1

    1

    0

    0

    0

    1


    имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  Z 2) X  ¬Y  ¬Z 3) X  ¬Y  ¬Z 4) ¬X  Y  Z



  1. Д

    X

    Y

    Z

    F

    1

    1

    1

    1

    1

    1

    0

    1

    1

    0

    1

    1


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  ¬Y  Z 3) X  Y  Z 4) X  Y  ¬Z



  1. Д

    X

    Y

    Z

    F

    0

    0

    0

    1

    1

    1

    0

    0

    0

    1

    1

    1


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  ¬Y  ¬Z 3) (X  Y)  ¬Z 4) (X  Y)Z



  1. Д

    X

    Y

    Z

    F

    0

    0

    0

    0

    0

    1

    1

    1

    1

    0

    0

    1


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) (X  ¬Y)Z 2) (X  Y)¬Z 3) X  (¬YZ) 4) X  Y  ¬Z



  1. Д

    X

    Y

    Z

    F

    1

    1

    0

    1

    1

    0

    1

    0

    0

    0

    1

    1


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) (X  Y)¬Z 3) (¬X  Y) Z 4) X¬Y  Z



  1. Д

    X

    Y

    Z

    F

    0

    1

    0

    1

    1

    1

    1

    1

    1

    1

    0

    0


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) (XY)Z 2) X (YZ) 3) ¬X  YZ 4) X  Y  ¬Z



  1. Д

    X

    Y

    Z

    F

    0

    0

    1

    1

    1

    0

    1

    0

    1

    1

    1

    1


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) (¬X  ¬Y)  Z 2) X  Y  Z 3) (XY)  Z 4) X  (Y  Z)



  1. Д

    X

    Y

    Z

    F

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    0


    ан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) (XZ) Y 2) X  Y  Z 3) X  Y  Z 4) X  (YZ)



X

Y

Z

F

1

1

0

1

1

0

1

0

0

0

1

1






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) (X  Y)¬Z 3) (¬X  Y) Z 4) X (¬Y  Z)



X

Y

Z

F

0

0

0

0

0

1

1

1

1

0

0

1






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) (X  ¬Y)Z 2) (X  Y)¬Z 3) X (¬YZ) 4) X  Y  ¬Z



X

Y

Z

F

1

0

0

1

0

1

1

0

0

0

0

1






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  Z 2) X  ¬Y  ¬Z 3) X  ¬Y  ¬Z 4) ¬X  Y  Z



X

Y

Z

F

1

0

0

0

0

0

1

1

0

0

0

0






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  ¬Z 2) ¬X  ¬Y  Z 3) ¬X  ¬Y  Z 4) X  Y  ¬Z



X

Y

Z

F

0

1

1

1

0

1

0

0

1

0

1

0






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  Z 2) ¬X  Y  ¬Z 3) X  ¬Y  ¬Z 4) X ¬ ¬Y  Z



X

Y

Z

F

0

1

1

0

1

1

1

1

0

0

1

1






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  ¬Y  ¬Z 2) ¬X  ¬Y  Z 3) ¬X  ¬Y  Z 4) X  ¬Y  ¬Z



X

Y

Z

F

1

1

1

1

1

1

0

1

1

0

1

1






  1. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  ¬Y  Z 2) X  Y  Z 3) X  Y  ¬Z 4) ¬X  Y  ¬Z



1 Источники заданий:

  1. Демонстрационные варианты ЕГЭ 2004-2009 гг.

  2. Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

  3. Якушкин П.А., Лещинер В.Р., Кириенко Д.П. ЕГЭ 2010. Информатика. Типовые тестовые задания. — М.: Экзамен, 2010.

  4. Якушкин П.А., Ушаков Д.М. Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. Информатика. — М.: Астрель, 2009.

  5. Абрамян М.Э., Михалкович С.С., Русанова Я.М., Чердынцева М.И. Информатика. ЕГЭ шаг за шагом. — М.: НИИ школьных технологий, 2010.




Похожие:

Тема : Построение таблиц истинности логических выражений iconТема: Логические законы и правила преобразования логических выражений
Цель: изучить законы логики, формировать умение применять логические законы при упрощении логических выражений
Тема : Построение таблиц истинности логических выражений icon¬(A  ¬B  C) ? 1) ¬A  b  ¬C 2) a  ¬B  C
Символом f обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения...
Тема : Построение таблиц истинности логических выражений iconКонтрольная работа по логике 1 Задание №1
Символом f обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения...
Тема : Построение таблиц истинности логических выражений iconЛекция Тема: Основы логики Что такое алгебра логики? Алгебра логики
Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или...
Тема : Построение таблиц истинности логических выражений iconИнформатика 11 класс
Преобразование логических выражений с использованием логических законов и правил преобразования
Тема : Построение таблиц истинности логических выражений iconТема : Составление запросов для поисковых систем с использованием логических выражений
Тема: Составление запросов для поисковых систем с использованием логических выражений
Тема : Построение таблиц истинности логических выражений iconТема: Логические выражения и таблицы истинности
Цель: учить учащихся выражать составное высказывание в виде логического выражения, строить таблицы истинности
Тема : Построение таблиц истинности логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Построение таблиц истинности логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Построение таблиц истинности логических выражений iconЛекция Решение логических задач методом рассуждений Что нужно знать : таблицы истинности логических операций «И», «или», «НЕ» (см презентацию «Логика»)
Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке:...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы