Методическое пособие по основам математической логики

Урок 1. Тема урока: «ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА»

Цели урока:

Образовательная – Ввести представление о логике как науке, ввести понятие логической функции и её месте в изучении информатики

Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Изучение нового материала

Логика – наука о формах и законах мышления.

Создал алгебру логики Дж. Буль (1816 -1864гг.). Всю жизнь он проработал учителем физики и математики. («Даже персидский трон не может принести такое наслаждение, как маленькое открытие») Подобно тому, как в алгебре изучают общие свойства числовых выражений, составленные из высказываний, так в математической логике изучают общие свойства выражений, составленные из высказываний с помощью логических операций.

Буль обозначал высказывания буквами. Простые высказывания – это переменные, сложные высказывания – функции этих переменных. Только эти переменные могут принимать только два значения: истинные высказывания – 1, ложные высказывания – 0.

В 1948 году Клод Шеннон использовал алгебру логики для проектирования релейных схем компьютера.

Функция F(х₁,х₂,…,х_т) называется логической, если сама функция и все её переменные принимают значения 0 или 1.

Такие функции удобно представлять с помощью таблиц истинности.

Пример: Логическая функция F(х₁,х₂х₃) принимает значения, равные 1, на наборах 0,3,6. Составить таблицу истинности.

N	X1	X2	X3	F
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	0

II.                Закрепление

Упражнение:  Составить таблицу истинности для логической функции F(х₁,х₂,х₃) =1 на наборах 1,4,7

III.              Итог урока

·         Что такое логика?

·         Кто создал алгебру логики?

·         Как использовал алгебру логики Клод Шеннон?

·         Какая функция называется логической?

IV.             Домашнее задание

1)      Выучить конспект

2)      Составить таблицу истинности для  логической функции F(х₁,х₂,х₃) =1 на наборах 2,5,7

Урок 2. Тема урока: «ОСНОВНЫЕ ЛОГИЧЕСКИЕ  ФУНКЦИИ»

Цели урока:

Образовательная –  Познакомить уч-ся с основными логическими функциями

Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Проверка домашнего задания

Вызывается ученик к доске для выполнения домашнего упражнения

Уч-ся отвечают на вопросы:

·         Что такое логика?

·         Кто создал алгебру логики?

·         Как использовал алгебру логики Клод Шеннон?

·         Какая функция называется логической?

II.                  Самостоятельная работа

Составить таблицу истинности для  следующих логических функций:

 В-1:          F(х₁,х₂,х₃) =1 на наборах 1,2,5,

В-2:           F(х₁,х₂,х₃) =1 на наборах 0,3,5,

В-3:           F(х₁,х₂,х₃) =1 на наборах 2,5,7

III.             Изучение нового материала

Логических функций всего 16. Мы с вами будем изучать 8.

1.      Операция НЕ – отрицание или инверсия. Это функция одной переменной. В результате этой операции образуется функция, значение которой равно 1, если переменная равна 0 и наоборот. Обозначается у= читается у= не х. таблица истинности имеет вид:

N	x	Y
0	0	1
1	1	0

2.      Операция И – логическое умножение или конъюнкция. В результате этой операции образуется функция от нескольких переменных, значение которой равно 1, если все переменные равны 1. Обозначается: у=х₁*х₂= х₁^х₂= х₁&х₂. Таблица истинности имеет вид:

N	X1	X2	y
0	0	0	0
1	0	1	0
2	1	0	0
3	1	1	1

3.      Операция ИЛИ – логическое сложение или дизъюнкция. В результате этой операции образуется функция нескольких переменных, значение которой равно 1,если хотя бы одна переменная равна 1. Обозначается у = х₁+х₂= х₁^х₂. Таблица истинности имеет вид:

N	X1	X2	y
0	0	0	0
1	0	1	1
2	1	0	1
3	1	1	1

IV.              Итог урока

·         С какими логическими операциями вы сегодня познакомились?

·         Какие новые слова вы сегодня изучили? Каков их смысл?

V.                Домашнее задание

1)      Выучить конспект

2)      Составить таблицу истинности для  логической функции F(х₁,х₂,х₃) =1 на наборах 1,2,5

Урок3. Тема урока :  "Основные логические функции"

Цели урока:

Образовательная -Продолжить знакомство с основными логическими функциями.

Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Проверка домашнего задания

Вызывается ученик к доске для выполнения домашнего упражнения

Уч-ся отвечают на вопросы:

·         С какими логическими операциями вы сегодня познакомились?

·         Какие новые слова вы сегодня изучили? Каков их смысл?

·         Как они обозначаются?

II.                 Изучение нового материала.

Продолжим изучение основных логических функций.                

4* Операция импликация (логическое следование)                

Обозначение: F = x₁→x₂ или F = x₁ + x₂.

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

N	X1	X2	F
0	0	0	1
1	0	1	1
2	1	0	0
3	1	1	1

5* Операция Пирса ( стрелка Пирса) ИЛИ - НЕ.

Функция  равна 1,  если     равны    нулю значения переменных.

Обозначается: у = х₁vх₂ = х₁+х₂ = х₁↓ х₂.

Составляем таблицу истинности по формуле: Один ученик у доски, остальные в тетрадях.

N	X1	X2	y
0	0	0	1
1	0	1	0
2	1	0	0
3	1	1	0

5* Операция штрих Шеффера И-НЕ.

В результате операции образуется функция, значение

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

Обозначается: у = х₁/х₂ = х1^х2

Составляем таблицу истинности по формуле: Один ученик у доски,  остальные в тетрадях.

N	X1	X2	y
0	0	0	1
1	0	1	0
2	1	0	0
3	1	1	0

7* Логическая операция равнозначности, эквивалентности.

В результате этой операции образуется функция, значение

которой равно 1 при равных значениях переменных.

Обозначается у = х₁~х₂. Составляем таблицу истинности.        Один ученик у доски,остальные в тетрадях

N	X1	X2	y
0	0	0	1
1	0	1	0
2	1	0	0
3	1	1	1

8* Логическая операция неравнозначности или

сложение по модулю 2.

В результате этой операции образуется функция,

значение которой равно 1 при неравных значениях переменных.

Обозначение: у = х₁ ♀ х₂

Составляем таблицу истинности по правилу: Один ученик у доски,

остальные в тетрадях.

N	X1	X2	y
0	0	0	0
1	0	1	1
2	1	0	1
3	1	1	0

И, ИЛИ, НЕ составляют полный набор.                                                             

III.              Итог урока.

·          С какими логическими операциями мы сегодня                         

познакомились?

·         По какому принципу составлялись таблицы истинности

этих функций?

IV.              Домашнее задание.

Выучить конспект.

Урок 4. Тема урока: "Переход от таблицы к формуле"

Цели урока:Образовательная - Познакомить учащихся с правилами перехода от таблицы истинности к формулам в дизъюктивной нормальной форме и конъюктивной нормальной форме, научить применять данные правила к конкретным функциям.

Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока:

I.                    Проверка домашнего задания.

·         С какими логическими операциями мы сегодня                          

познакомились?

·         По какому принципу составлялись таблицы истинности

этих функций?

II. Изучение нового материала.

Сегодня мы познакомимся с вами с правилами,                           

по которым можно по таблице истинности                                

составить формулы логических функций.

Существует дизъюктивная нормальная форма (ДНФ)

и конъюктивная нормальная форма (КНФ) таких

представлений.

Запишем правило, а затем, следуя ему, составим эти формулы.

Необходимо построить схему так, чтобы она работала как

 таблица истинности.

В ДНФ:

1) Выбирают строки, где значение функции равно 1.

2) Для этих строк записывается произведение переменных;

те переменные, значение которых равно 0, входят в эту конъюнкцию

 с отрицанием.

3) Взяв дизъюнкцию этих конъюнкций, получим выражение в ДНФ

(т.е. сложим эти  произведения).

В КНФ:

1) Выбирают строки, где значение функции равно 0.

2) Для этих строк записывается сумма переменных;

те переменные, значение которых равно 1, берутся

с отрицанием.

3) перемножить данные дизъюнкции.

Рассмотрим пример: Пусть функция F(x1,x2,x3) = 1

на наборах 1, 2, 4, 7. Составим для неё таблицу истинности.    Уч-ся активно помогают в составлении таблицы.

N	X1	X2	X3	F	Для ДНФ	Для КНФ
0	0	0	0	0		Х1+х2+х3
1	0	0	1	1	_  _ Х1*х2*х3
2	0	1	0	1	_    _ Х1*х2*х3
3	0	1	1	0		_ Х1+х2+х3
4	1	0	0	1	_ _ Х1*х2*х3
5	1	0	1	0		_    _ Х1+х2+х3
6	1	1	0	0		_ _ Х1+х2+х3
7	1	1	1	1	Х1*х2*х3

          _ _           _      _ _

F(ДНФ) =  Х₁*х₂*х₃+ Х₁*х₂*х₃+ Х₁*х₂*х₃+ Х₁*х₂*х₃

                                                  _      _     _     _ _   

F(КНФ) =( Х₁+х₂+х₃  )( Х₁+х₂+х₃ )( Х₁+х₂+х₃ )( Х₁+х₂+х₃ )

II.                Закрепление.

Составить аналитическое выражение в КНФ и ДНФ для функции от

 3-х переменных, значения которой равны1 на наборах 1,4,6

Решение:

N	X1	X2	X3	F	Для ДНФ	Для КНФ
0	0	0	0	0		Х1+х2+х3
1	0	0	1	1	_ _ Х1*х2*х3
2	0	1	0	1		_ _ Х1+х2+х3
3	0	1	1	0		_ Х1+х2+х3
4	1	0	0	1	_ _ Х1*х2*х3
5	1	0	1	0		_    _ Х1+х2+х3
6	1	1	0	0	_ Х1*х2*х3
7	1	1	1	1		_  _ _ Х1*х2*х3

 F(ДНФ)=_ _       _  _        _

Х₁*х₂*х₃+Х₁*х₂*х₃+ Х₁*х₂*х₃                                                          

                        _          _ _     _    _    _  _ _

F(КНФ) = (Х₁+х₂+х₃ )( Х₁+х₂+х₃ )( Х₁+х₂+х₃ )( Х₁+х₂+х₃)( Х₁+х₂+х₃) IV.        Домашнее задание.1) Выучить правила перехода от таблицы к формуле                     2) Составить аналитическое выражение в КНФ и в ДНФдля функции от 3-х переменных, значение которой равно 1на наборах 0,3,6.

Урок5. Тема урока: "Переход от таблицы к формуле"

Цели урока: Образовательная -Закрепить полученные знания  

 Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Проверка домашнего задания

Вызывается ученик к доске для выполнения домашнего упражнения

Ответы домашнего задания

                _      _      _         _     _   _  _

F(КНФ) = (х1+х2+х3)(х1+х2+х3)(х1+х2+х3)(х1+х2+х3)(х1+х2+х3)                                 _ _ _ _          _

                        F(ДНФ) = х1х2х3+х1х2х3+х1х2х3

·         По какому правилу осуществляется переход от таблицы к формуле в ДНФ и КНФ?

II.                 Самостоятельная работа

Составить аналитическое выражение в КНФ и в ДНФдля функции от 3-х переменных:

В-1:        F(x1,x2,x3) = 1на наборах 1, 2, 3,4

В-2: F(x1,x2,x3) = 1на наборах  2, 4, 6,7

В-3:     F(x1,x2,x3) = 1на наборах  4,5,6 7

Ответы для контроля:

                        _     _  _   _     _  _  _

В-1:     F(КНФ) = (х1+х2+х3)(х1+х2+х3)(х1+х2+х3)(х1+х2+х3)

         _ _    _   _  _        _ _

F(ДНФ) = х1х2х3+х1х2х3+х1х2х3+х1х2х3

                                _      _  _   _     _

 В-2: F(КНФ) = (х1+х2+х3)(х1+х2+х3)(х1+х2+х3)(х1+х2+х3)       _   _   _  _     _

F(ДНФ) = х1х2х3+х1х2х3+х1х2х3+х1х2х3

                                                               _      _              _      _   В-3: F(КНФ) = (х1+х2+х3)(х1+х2+х3)(х1+х2+х3)(х1+х2+х3

            _ _    _        _

 F(ДНФ) = х1х2х3+х1х2х3+х1х2х3+х1х2х3

III.             Итог урока

Провести анализ самостоятельной работы

IV.             Домашнее задание

Составить аналитическое выражение в КНФ и в ДНФдля функции от 3-х переменных, значения которой рвны1 на наборах 3,6,7

Уроки 6,9.Тема урока: "Законы алгебры логики"

Цели урока: Образовательная- Познакомить учащихся с основными законами алгебры логики и показать некоторые приёмы упрощения логических функций Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Проверка домашнего задания

Вызывается ученик к доске для выполнения домашнего упражнения

Ответы домашнего задания

II.                Изучение нового материала.

Новый материал даётся учителем лекционно

Законы алгебры логики нужны для упрощения логических выражений

 1* Коммуникативность:

Х*у=у*х

Х+у=у+х

2* Ассоциативность:

X*(y*z)=(x*y)*z=x*y*z

X+(y+z)=(x+y)+z=x+y+z

3* Дистрибутивность:

X(y+z)=xy+xz

X+yz=(x+y)(x+z)

Доказать законы можно с помощью таблиц истинности. Составлять таблицы истинности нужно с помощью уч-ся

N	X	Y	Z	X(y+z)	Xy+xz	X+yz	(x+y)(x+z)
0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	0
2	0	1	0	0	0	0	0
3	0	1	1	0	0	1	1
4	1	0	0	0	0	1	1
5	1	0	1	1	1	1	1
6	1	1	0	1	1	1	1
7	1	1	1	1	1	1	1

                        4*Правило де Моргана:   __   _ _    а) ху = х+у   ___   _ _б) х+у = х*уДоказать эти свойства с помощью таблиц истинности. Один ученик у доски, остальные в тетрадях

N	X	Y	___ X*y	_ _ X+y	___ X+y	_ _ X*y
0	0	0	1	1	1	1
1	0	1	1	1	0	0
2	1	0	1	1	0	0
3	1	1	0	0	0	0

 Следствия законов 1-4:1) х*х*х*...*х = х - отсутствие степеней и2) х+х+х...+х = х     коэффициентов            _3) х + х = 1- закон исключённого третьего        _4) х*х = 0 - закон противоречия    =5) х = х - двойное отрицаниеСвойства констант:6)1 + F = 17) 1*F = F8) F*0 = 09) 0 + F = F

Правило склеивания:Склеиваются соседние конъюнкции, которые отличаются представлением одной переменной.                              _                        _Пример: х1х2х3 + х1х2х3 = х1х2(х3+х3) = х1х2*1 = х1х2Правило поглощения: (следствие распределительного закона)х1 + х1х2 + х1х2х3 = х1                                   _   Правило свёртки: х1 + х1х2 = х1 + х2                                             _                                   _Правило расширения: х1х2 + х1х3 + х2х3 = х1х2 + х1х3Пример: Упростить функцию F(x1,x2,x3) = 1 на наборах 3,5,6,7. Один ученик составляет для ДНФ таблицу истинности. Второй ученик составляет формулу, третий упрощает её

N	X1	X2	X3	F	Для ДНФ
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1	_ Х1*х2*х3
4	1	0	0	0
5	1	0	1	1	_ Х1*х2*х3
6	1	1	0	1	_ Х1*х2*х3
7	1	1	1	1	Х1*х2*х3

                          _               _                 _F(x1,x2,x3)= х1х2х3 + х1х2х3 + х1х2х3 + х1х2х3 =       _            _        _          = х2х3(х1+х1)+х1х2х3+х1х2х3 = х2х3+х1х2х3+х1х2х3 =             _             _                      _       _=х3(х2+х1х2)+х1х2х3 =х3(х2+х1)(х2+х2)+х1х2х3 =                   _                                 _                                                _х2х3+х1х3+х1х2х3 =х2х3+х1(х3+х2х3) = х2х3+ х1(х3+х2)(х3+х3) == х2х3+х1х3+х1х2.

III.  Домашнее задание.

Урок 8. Тема урока:  "Типовые задачи по преобразованию логических функций"

Цели урока: Образовательная-Познакомить учащихся с порядком анализа логической функции

 Развивающая – развивать познавательный интерес учащихся, умения применять полученные знания на практике.

Воспитательная – повысить уровень информационной культуры учащихся.

Ход урока

I.                   Проверка домашнего задания

·         Какие законы алгебры логики вы знаете?                        Отвечают на вопросы

·         Как доказывается истинность этих законов?

·         Какие следствия из законов вы знаете? II.           Изучение нового материала.Цель анализа - составление таблицы истинности. Слушают и записывают конспектПорядок анализа логической функции:1) Раскрывая скобки и инверсии, представить функцию в ДНФ.2) Домножить каждую неполную конъюнкцию( т.е. ту, в       _которую входят не все переменные или их отрицания) на 1 = х+х,где х = отсутствующая в данной конъюнкции переменная.3) Привести одинаковые конъюнкции по формуле х+х=х; получится СДНФ.

4)Заменить в каждой конъюнкции каждую переменную на 1,  отрицание-на 0.

5) Каждому полученному таким образом цифровому набору сопоставить в таблице истинности значение 1, а всем остальным наборам – 0

Упражнение: Выполнить анализ функции F(x1,x2,x3)=х1х2х3

Решение:             _            _

F(x1,x2,x3)=х1х2(х3+х3)+х1х3( х2+х2) =

              _          _                 _    _    

= х1х2х3+х1х2х3+х1х2х3+х1х2х3 = х1х2х3+х1х2х3+х1х2х3

                                                               1  0  1    1  0  0    1  1  0

Таким образом, F(x1,x2,x3) = 1 на наборах 7,6,5.

Получаем следующую таблицу истинности

N	X1	X2	X3	F
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

II.                Закрепление

Упражнение: 1) Выполнить анализ функции F(x1,x2,x3)=х2х3+х1х3

Решение:             _            _

F(x1,x2,x3)=х2х3(х1+х1)+х1х3( х2+х2) =

              _           _                 _    _    

= х1х2х3+х1х2х3+х1х2х3+х1х2х3 = х1х2х3+х1х2х3+х1х2х3

                                                                       1 1 1   1 1 0  1 0 1

Таким образом, F(x1,x2,x3) = 1 на наборах 7,6,5.

Таблицу истинности смотри выше.                    ___

2)Выполнить анализ функции F(x1,x2,x3)=х1(х2х3)

              ____     __ __    __   __   __     _

Решение: F=х1(х2х3)=х1(х2+х3)=х1х2+х1х3=х1х2(х3+х3)+

  _     __    __     _  _      _   _ _     _     _ _       _

х1х3(х2+х2)=х1х2х3+х1х2х3+х1х2х3+х1х2х3=х1х2х3+х1х2х3+х1х2х3

                                                                                         1 0 1  1 0 0  1 1 0

 Таким образом, F(x1,x2,x3) = 1 на наборах 4,6,5.

N	X1	X2	X3	F
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	0

III.              Итог урока

·         Каков порядок анализа логической функции?

·         По каким законам раскрываются скобки и инверсии?

IV.              Домашнее задание.                                 ___ 

Выполнить анализ логической функции: F = х1х3