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

Методическая разработка по теме:

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

Ржев 2011

Содержание.

1. Введение ………………………………………………..………2
2. Немного теории……………………………………………..…3
3. Построение таблиц истинности логических выражений...6
4. Приложение 1 (примеры заданий ЕГЭ)……………………10
5. Ответы…………………………………………………………13

   ---

Введение.

Для успешной сдачи ЕГЭ по предмету  «Информатика и ИКТ» необходимо уметь строить таблицы истинности логических выражений. Во всех учебниках указан метод построения таблиц истинности, который, на мой взгляд, является достаточно сложным и запутанным. Я использую другой способ построения таблиц истинности логических выражений. Ученики без проблем осваивают этот способ очень быстро, так как он основан на том же методе, что мы используем на уроках математики в примерах на несколько действий. Мы вычисляем значение одного действия и результат подписываем над действием.

Данная разработка будет полезна учителям информатики и ИКТ и учащимся для подготовки к ЕГЭ по информатике.

Немного теории.

Все логические задачи, предлагаемые на ЕГЭ, сводятся к работе с логическими выражениями и заключаются либо в построении таблицы истинности логического выражения, либо в преобразовании логического выражения (приведения к каноническому виду).
Логические выражения состоят из логических операций, примененных к логическим элементам.
Логические элементы могут принимать значения 0 или 1.
     Таблица истинности логического выражения - это таблица, содержащая все возможные комбинации значений переменных, входящих в это выражение, и значения выражения, соответствующие каждой из этих комбинаций.

Для построения таблиц истинности сложной функции необходимо знать таблицы истинности элементарных функций. (Уже на этом этапе желательно давать таблицы в таком виде для того, чтобы приучить к записи)
Основных логических операций всего 3:
1) «не А» - отрицание (инверсия, дополнение) производится над одним
элементом. Обозначается горизонтальной чертой сверху: А, или знаком ┐А. 

Таблица истинности отрицания (красным – значения переменной, чёрным – значение функции).

┐А                  

1 0

0 1

Если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным.
2) «А и В» - логическое умножение (логическое "и", конъюнкция) производится над двумя логическими элементами и обозначается обычно знаками х или /\ (а бывает, что и &).

Таблица истинности конъюнкции.

А & В

0  0  0

0  0  1

1  0  0

1  1  1

Каждая логическая функция имеет исключение (одно значение отличается от всех остальных). Именно его и  надо запоминать.

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

3) «А или В» - логическое сложение (логическое "или", дизъюнкция) производится над двумя элементами и обозначается обычно знаками + или V.

Таблица истинности дизъюнкции.

А V В

0  0  0

0  1  1

1  1  0

1  1  1

Логическое сложение ложно тогда и только тогда, когда оба простых логических выражения ложны, и истинно, если хотя бы одно из простых логических выражений истинно.

4) «если А то В» - логическое следование (импликация)  производится над двумя элементами и обозначается обычно знаком  →. Данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

Таблица истинности импликации.

А → В

0  1  0

0  1  1

1  0  0

1  1  1

Логическое следование ложно, когда из истины следует ложь.

5) «А тогда и только тогда когда В» - логическая равнозначности (эквивалентность) производится над двумя элементами и обозначается обычно знаком ≡, или ↔.

Таблица истинности эквивалентности.

А ≡ В

0  1  0

0  0  1

1  0  0

1  1  1

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

Обращаю ваше внимание, что отрицание в моём методе надо записывать ┐. Если формула записана в виде А V (В V С), то её необходимо переписать в виде А V ┐(В V С), а А V (В V С) = А V (┐В V ┐С). На этот переход необходимо обратить внимание и потренироваться выполнять.

Когда вы записываете конъюнкцию /\, дизъюнкцию V это почти всегда ведёт к ошибке перепутать их при составлении таблиц истинности.. Поэтому конъюнкцию всегда советую записывать & или х, для того что бы не перепутать их таблицы истинности.

Когда всё это усвоено и отработано, то переходим к построению таблиц истинности сложных функций.

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

Порядок выполнения логических операций в сложном логическом выражении.

1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.

┐     &    V    →     ≡

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

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить последовательность выполнения логических операций (расставить порядок действий, как в математике);
2. Определить количество различных переменных (простых выражений);(n)
3. Определить количество строк (количество различных наборов 0 и 1):

количество строк = 2n ,

n - количество простых высказываний;

4. Подписать различные значения переменных, используя следующее правило: под первой переменной записать 2n/2   0, а затем такое же количество 1; под второй переменной (и на каждом следующем шаге) в два раза меньше 0, чем в предыдущей переменной, и в 2 раза меньше 1; последняя переменная – всегда чередование 0 и 1.
5. Выполнить логические операции по порядку. При этом зачёркиваем столбцы, которые уже обработали. Для каждого действия берём первые незачёркнутые значения справа и слева.
6. Столбец, полученный в результате выполнения последнего действия, и есть результат.

Рассмотрим данный алгоритм на конкретном примере.

Составить таблицу истинности логического выражения ┐А&(B V ┐C)

Решение:

Перепишем данную формулу так, чтобы внизу было достаточно места

1 шаг алгоритма (порядок действий)

3           4          2     1

┐А&(B V ┐C)

2 шаг алгоритма (количество различных переменных)

В данном выражении 3 различных переменных. n=3.

3 шаг алгоритма (найти количество строк)

23=8

8 строк.

4 шаг алгоритма (заполняем таблицу)

3           4          2     1

┐А&(B V ┐C)

    0

    0                                     первая переменная А половина 0, половина 1.

0

0

1

1

1

1

3           4          2     1

┐А&(B V ┐C)

    0     0

    0     0                              

0     1

0     1                         вторая переменная В два 0, две 1 .

1     0

1     0

1     1

1     1

3           4          2     1

┐А&(B V ┐C)

    0     0        0

    0     0        1                      

0     1        0

0     1        1              последняя переменная С чередование 0 и 1 .

1     0        0

1     0        1

1     1        0

1     1        1

5 шаг алгоритма (выполнение действий)

3           4          2     1

┐А&(B V ┐C)

    0     0     1 0

    0     0     0 1                      

0     1     1 0

0     1     0 1          выполнили первое действие – отрицание («всё наоборот»)

1     0     1 0          значения переменной С «зачеркнули».

1     0     0 1

1     1     1 0

1     1     0 1

3           4          2     1

┐А&(B V ┐C)

    0     0  1 1 0

    0     0  0 0 1                      

0     1  1 1 0

0     1  1 0 1          выполнили второе действие – дизъюнкцию (ложно тогда и только

1     0  1 1 0          тогда, когда оба простых логических выражения ложны) 

1     0  0 0 1           «обработанные столбцы «зачеркнули»

1     1  1 1 0

1     1  1 0 1

3           4          2     1

┐А&(B V ┐C)

1  0     0  1 1 0

1  0     0  0 0 1                      

1  0     1  1 1 0

1  0     1  1 0 1          

0  1     0  1 1 0        

0  1     0  0 0 1          

0  1     1  1 1 0

0  1     1  1 0 1

3           4          2     1

┐А&(B V ┐C)

1  0 1  0  1 1 0

1  0 0  0  0 0 1                      

1  0 1  1  1 1 0

1  0 1  1  1 0 1          

0  1 0  0  1 1 0        

0  1 0  0  0 0 1          

0  1 0  1  1 1 0

0  1 0  1  1 0 1

Результат

Если в логическом выражении одна переменная встречается несколько раз, то при заполнении таблицы записываем ей одинаковые значения. Например:

А V В & А & В

0      0      0      0           В данном выражении две различные переменные,

0      1      0      1            поэтому 4 строки.

1      0      1      0

1      1      1      1

Приложение №1 (задания ЕГЭ с сайта http://www.egeinf.ru:8080/or/inf/Main)

1. Задание A8 (№ 212194)

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

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

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

Варианты ответа

2. Задание A8 (№ 212196)

Дана таблица истинности 4-х функций от трех логических переменных: F1(X,Y,Z), F2(X,Y,Z), F3(X,Y,Z), F4(X,Y,Z):

Какая из данных функций соответствует выражению ?

Варианты ответа

1. F1             2. F2         3. F3         4. F4

3. Задание A8 (№ 212197)

Дана функция от трех переменных . При каком из указанных значений аргументов X, Y, Z функция принимает значение, равное 1?

Варианты ответа

1. X=1, Y=0, Z=0        2. X=0, Y=0, Z=0     3. X=1, Y=1, Z=0       4. X=0, Y=0, Z=1

4. Задание A8 (№ 212198)

Дана функция от трех переменных . При каком из указанных значений аргументов X, Y, Z функция принимает значение, равное 0?

Варианты ответа

1. X=1, Y=0, Z=0        2. X=1, Y=1, Z=0     3. X=0, Y=1, Z=0       4. X=0, Y=0, Z=1

1. Задание A8 (№ 212199)

Для какого числа различных наборов аргументов X, Y логическая функция  принимает значение, равное 1?

Варианты ответа

1. 0           2. 1          3. 2         4. 3

2. Задание A8 (№ 212201)

Для какого числа различных наборов аргументов X, Y, Z логическая функция  принимает значение, равное 1?

Варианты ответа

1. 1          2. 3          3. 6         4. 7

3. Задание A13 (№ 236896)

Для какого числа X истинно высказывание ?

Варианты ответа

1. 1           2. 2          3. 3         4. 4

4. Задание A13 (№ 236902)

Для какого символьного набора истинно высказывание:

Первая буква гласная  (Третья буква согласная)?

Варианты ответа

1. AMKIK           2. KAINA          3. IMMAK         4. IICAI

5. Задание A13 (№ 236904)

Для какого слова истинно высказывание

(1 буква — гласная)  (3 буква — согласная)  (4 буква — гласная)?

Варианты ответа

1. abcde        2. bceda     3. abedc       4. Bcade

6. Задание A13 (№ 236910)

Для каких из указанных значений X и Y истинно высказывание:

?

Варианты ответа

1. X=0, Y=0           2. X=0, Y=0,5       3. X=0, Y=1       4. X=0,5, Y=0,5

7. Задание A13 (№ 236909)

Для какого символьного набора ложно высказывание:

((Первая буква — гласная)   (Вторая буква — гласная))  (Третья буква — согласная)

Варианты ответа

1. Крот        2. Атака     3. Арбуз      4. Оазис

8. Задание A13 (№ 236913)

Для каких из указанных значений X и Y ложно высказывание:

?

Варианты ответа

1. X=0, Y=-0,5            2. X=0,5, Y=-0,75         3. X=0,25, Y=-0,5       4. X=0,5, Y=-0,5

Ответы.

1. 4

2. 2

3. 1

4. 3

5. 2

6. 2

7. 3

8. 2

9. 3

10. 2

11. 3

12. 1