Алгебра логики. Определение формы сложных высказываний, построение таблиц истинности

Вид материалаУрок

Содержание


Ваш приезд не является ни необходимым, ни желательным
С= Нервы привыкнут раздражаться
Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послуш
Алгоритм построения таблицы истинности
Демократ- это человек, исповедующий демократические убеждения
Дождь будет или дождя не будет
Дополнительное задание
Карточка для домашней работы
Люди получают высшее образование тогда и только тогда, когда они заканчивают институт, университет или академию
Подобный материал:
Урок №21

Алгебра логики. Определение формы сложных высказываний, построение таблиц истинности

(урок 2 по теме; тип: урок закрепления)

Цели урока:

- проверить знание терминологии по теме Логические операции;

- научить записывать формы сложных высказываний, строить таблицы истинности сложных высказываний;

- ввести понятия: сложное высказывание, тождественно истинное высказывание и тождественно ложное высказывание;

- развитие логического и пространственного мышления, памяти, внимательности;

- повышение интереса к предмету;

- воспитание культуры общения.

Этапы урока
    1. Организационный момент. Постановка цели урока. 2 мин.
    2. Проверка домашнего задания. 10 мин.
    3. Контроль знаний (диктант). 9 мин.
    4. Закрепление. 20мин.
    5. Подведение итогов урока. 2 мин.
    6. Постановка домашнего задания. 2 мин.

Ход урока

Проверяем письменное домашнее задание.

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

Вариант 1.

Вариант 2.

1. «А импликация В конъюнкция С» (ответ: АВ·С)

1. «А дизъюнкция В эквивалентность С»

(ответ: АВ С)


2. Ответ: АВ А·В




2. Ответ: А·СВ




3. Ответ: А·ВСАС


3. Ответ: АСВ·D

4.Логическое сложение

4.Логическое умножение

5. Логическое равенство

5. Логическое следование

Для проверки можно открыть обратную сторону доски с правильными ответами.

Переходим к следующему материалу.


§3. Алгебра логики. Определение формы сложных высказываний,

построение таблиц истинности

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

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

Всякое сложное высказывание принимает значение 1 или 0 в зависимости от значения простых высказываний, из которых оно построено.

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

Сложные высказывания часто называют формулами логики высказываний.

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

Приведём примеры определения формулы сложного высказывания.
  1. Е= Ваш приезд не является ни необходимым, ни желательным.

Составляющие простые высказывания:

А= Ваш приезд необходим; В= Ваш приезд желателен.

Формула сложного высказывания: Е= &.

Определите самостоятельно формы сложных высказываний:
  1. К= Поиски врага длились уже три часа, но результатов не было, притаившийся враг ничем себя не выдавал.
  2. Р=Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.
  3. Т= Если у меня будет свободное время и не будет дождя, то я не буду писать сочинение, а пойду на дискотеку.
  4. X= Лошадь погибает от одного грамма никотина, но я не лошадь, следовательно, курить вредно.

Теперь для тренировки попробуем выполнить обратное задание.

6. Пусть дана формула сложного высказывания: (&)(&·D) и составляющие простые высказывания:

А= Человек с детства давал нервам властвовать над собой;

В= Человек в юности давал нервам властвовать над собой;

С= Нервы привыкнут раздражаться;

D= Нервы будут послушны.

Какая фраза на естественном языке может быть сформулирована по данной форме?

Е= Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны. (К. Д. Ушинский.)

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


1

2

3

4

5

А

В





&

0

0

1

1

1

0

1

1

0

0

1

0

0

1

0

1

1

0

0

0

Алгоритм построения таблицы истинности
  1. Подсчитать n- количество переменных в формуле.
  2. Определить число строк в таблице m=2n+ 2, где 2n -количество двоичных наборов, 2-строки заголовка.
  3. Подсчитать количество логических операций в формуле.
  4. Установить последовательность выполнения логических операций с учётом скобок и приоритетов.
  5. Определить количество столбцов в таблице: число переменных плюс число операций.
  6. Выписать наборы входных переменных с учётом того, что они представляют собой натуральный ряд n- разрядных чисел от 0 до 2n-1.
  7. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью.

Построим по данному алгоритму таблицу истинности для формулы А& из примера 2.

Порядок выполнения логических операций будет следующим: инверсия С, инверсия В, конъюнкция, импликация.

1

2

3

4

5

6

7

А

В

С





(1)&(5)

(4)(6)

0

0

0

1

1

0

0

0

0

1

0

1

0

1

0

1

0

1

0

0

0

0

1

1

0

0

0

1

1

0

0

1

1

1

1

1

0

1

0

1

1

1

1

1

0

1

0

0

0

1

1

1

0

0

0

1


§4. Алгебра логики. Тождественно истинные, тождественно ложные и эквивалентные высказывания

Если сложное высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1.)

Например, высказывание Демократ- это человек, исповедующий демократические убеждения всегда истинно, т. е. является тавтологией.

Все математические, физические законы и законы других наук являются тавтологиями.

Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).

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

Пример. Построим таблицы истинности для формул А и А&

А

А&

1

2

3

А



А

0

1

1

1

0

1




1

2

3

А



А&

0

1

0

1

0

0




Первое высказывание будет тождественно истинным. Например, Дождь будет или дождя не будет. Второе высказывание тождественно ложное. Например, Компьютер включен, и компьютер не включен (выключен).

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

Высказывания А и В равносильны (А=В) тогда и только тогда, когда их эквивалентность АВ является тождественно истинным высказыванием.

В качестве примера рассмотрим два высказывания:

X= Не может быть, что Матроскин выиграл приз и отказался от него.

X= .

Y= Или Матроскин не отказался от приза, или не выиграл его.

Y=.

Чтобы доказать равносильность сложных высказываний X и Y, достаточно построить из таблицы истинности. Объединим эти две таблицы в одну:

1

2

3

4

5

6

7

8

А

В





(1)& (2)

X=

Y=(3)(4)

(6)(7)

0

0

1

1

0

1

1

1

0

1

1

0

0

1

1

1

1

0

0

1

0

1

1

1

1

1

0

0

1

0

0

1

Существуют два варианта рассуждений:
  1. Так как значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то по определению X равносильно Y.
  2. Так как 8-й столбец содержит одни единицы, то эквивалентность X и Y тождественна истина, значит, X и Y тождественно истинна, значит, X и Y равносильны.

Дополнительное задание

Формализуйте приведённое ниже высказывание и постройте для него таблицу истинности:

F= {Если все стороны четырёхугольника равны, а он не является квадратом, то один из его углов не является прямым}

Подведение итогов урока

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

Кратко повторить алгоритм построения таблицы истинности.

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

Постановка домашнего задания
  1. Разобрать конспект урока.
  2. Выучить все определения и алгоритм построения таблицы истинности из конспекта урока.
  3. Выполнить упражнения с карточки в тетради. Листочек с классной работой вклеить в тетрадь, карточку принести.

Все пункты заданий на карточке учитель должен прокомментировать.

Карточка для домашней работы
  1. Определите формы следующих сложных высказываний:

А) Е= Вчера было пасмурно, а сегодня ярко светит солнце.

Б) К= И добродетель стать пороком может, когда её неправильно приложат. (У. Шекспир.)

В) Р= Люди получают высшее образование тогда и только тогда, когда они заканчивают институт, университет или академию.
  1. Постройте таблицы истинности следующих сложных высказываний и определите, являются ли эти высказывания тождественно истинными:

А) АВА; Б) А(ВА·В); *в) (АВ) А)
  1. Докажите эквивалентность следующих высказываний:

F1= {Если одно слагаемое делиться на 3 и сумма делится на 3, то и второе слагаемое делится на 3};

F2= {Если одно слагаемое делится на три, а второе не делится на 3, то сума не делится на три}.
  1. Дополнительное задание.

Выберите высказывание, эквивалентное данному не (неА и не(В и С)).

А) А и В или С и А; Б) (А или В) и (А или С); В) А и (В или С); Г) А или (не В или не С).




1 (по книге В. Лысковой и Е. Ракитиной «Логика в информатике)