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

Вид материала

Урок

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

Подобный материал:

• Лабораторная работа по теме «Построение таблиц истинности с помощью электронных таблиц, 32.44kb.
• Построение таблиц истинности сложных высказываний, 104.54kb.
• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.
• «Построение таблиц истинности», 125.84kb.
• Урок информатики по теме "Основы логики, таблицы истинности", 123.74kb.
• Логика высказываний. Основные понятия и определения. Логические функции одной и двух, 6.36kb.
• «Построение таблиц истинности логических выражений с использованием электронных таблиц», 487.41kb.
• Задачи: Повторить основные понятия логики. Решить задачи: на построение логических, 274.05kb.
• Лекция Логические основы компьютеров , 369.25kb.
• Программа дисциплины Математическая логика Семестр, 13.41kb.

Урок №2¹

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

(урок 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. Е= Ваш приезд не является ни необходимым, ни желательным.
   

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

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

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

Определите самостоятельно формы сложных высказываний:

2. К= Поиски врага длились уже три часа, но результатов не было, притаившийся враг ничем себя не выдавал.
   
3. Р=Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.
   
4. Т= Если у меня будет свободное время и не будет дождя, то я не буду писать сочинение, а пойду на дискотеку.
   
5. 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=2ⁿ+ 2, где 2ⁿ -количество двоичных наборов, 2-строки заголовка.
   
3. Подсчитать количество логических операций в формуле.
   
4. Установить последовательность выполнения логических операций с учётом скобок и приоритетов.
   
5. Определить количество столбцов в таблице: число переменных плюс число операций.
   
6. Выписать наборы входных переменных с учётом того, что они представляют собой натуральный ряд n- разрядных чисел от 0 до 2ⁿ-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. Выполнить упражнения с карточки в тетради. Листочек с классной работой вклеить в тетрадь, карточку принести.
   

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

Карточка для домашней работы

Определите формы следующих сложных высказываний: А) Е= Вчера было пасмурно, а сегодня ярко светит солнце. Б) К= И добродетель стать пороком может, когда её неправильно приложат. (У. Шекспир.) В) Р= Люди получают высшее образование тогда и только тогда, когда они заканчивают институт, университет или академию.

Постройте таблицы истинности следующих сложных высказываний и определите, являются ли эти высказывания тождественно истинными: А) АВА; Б) А(ВА·В); *в) (АВ)(В А)

Докажите эквивалентность следующих высказываний: F1= {Если одно слагаемое делиться на 3 и сумма делится на 3, то и второе слагаемое делится на 3}; F2= {Если одно слагаемое делится на три, а второе не делится на 3, то сума не делится на три}.

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