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

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



НазваниеТема : Построение таблиц истинности логических выражений
страница1/4
Дата конвертации24.06.2012
Размер499.58 Kb.
ТипДокументы
  1   2   3   4

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

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


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

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

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

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

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

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

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

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

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

AB эквивалентность (равносильность)

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

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

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

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

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

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

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

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

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

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

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

  • логическое следование (импликация) А?В равна 0 тогда и только тогда, когда из A (посылка) истинна, а B (следствие) ложно

  • эквивалентность АB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1

П

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.
^

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


Дано логическое выражение, зависящее от 5 логических переменных:

X1  ¬X2  X3  ¬X4  X5

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

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

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

  1. перепишем выражение в других обозначениях:


  2. таблица истинности для выражения с пятью переменными содержит 25 = 32 строки (различные комбинации значений этих переменных)

  3. логическое произведение истинно в том и только в том случае, когда все сомножители равны 1, поэтому только один из этих вариантов даст истинное значение выражения, а остальные 32 – 1 = 31 вариант дают ложное значение.

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




Похожие:

Тема : Построение таблиц истинности логических выражений iconПостроение таблиц истинности логических выражений Приоритет логических операций
При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:...
Тема : Построение таблиц истинности логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Построение таблиц истинности логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Построение таблиц истинности логических выражений iconПроверочная работа по теме «Таблицы истинности логических выражений»
Выбрать составное высказывание, имеющее ту же таблицу истинно­сти, что и не (не а и не (В и С))
Тема : Построение таблиц истинности логических выражений iconЛабораторная работа по теме «Построение таблиц истинности с помощью электронных таблиц Excel» Цель работы : познакомиться с логическими функциями Excel, научиться строить таблицы истинности сложных высказываний
Цель работы: познакомиться с логическими функциями Excel, научиться строить таблицы истинности сложных высказываний
Тема : Построение таблиц истинности логических выражений iconТема : Составление запросов для поисковых систем с использованием логических выражений
Тема: Составление запросов для поисковых систем с использованием логических выражений
Тема : Построение таблиц истинности логических выражений iconАлгебра логики Мышление Логика – наука о формах и способах мышления
Алгебра логики- раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности)...
Тема : Построение таблиц истинности логических выражений iconСовершенная дизъюнктивная, совершенная конъюнктивная нормальная форма
Мы знаем 2 способа задания логических функций: формулой и таблицей истинности. По формуле легко составляется таблица. На практике...
Тема : Построение таблиц истинности логических выражений iconДомашнее задание: Составление таблиц истинности

Тема : Построение таблиц истинности логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Разместите кнопку на своём сайте:
Документы


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

Разработка сайта — Веб студия Адаманов