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

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

Цели урока:

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

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

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

Ход урока

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

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

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

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

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

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

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

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

N

X₁

X₂

X₃

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

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

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

3. Итог урока

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

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

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

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

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

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

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

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

Цели урока:

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

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

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

Ход урока

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

N

x

Y

0

0

1

1

1

0

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

   N

   X₁

   X₂

   y

   0

   0

   0

   0

   1

   0

   1

   0

   2

   1

   0

   0

   3

   1

   1

   1

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

N

X₁

X₂

y

0

0

0

0

1

0

1

1

2

1

0

1

3

1

1

1

4. Итог урока

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

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

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

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

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

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

Цели урока:

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

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

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

Ход урока

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

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

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

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

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

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

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

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

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

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

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

N

X₁

X₂

F

0

0

0

1

1

0

1

1

2

1

0

0

3

1

1

1

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

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

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

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

N

X₁

X₂

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

0

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

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

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

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

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

N

X₁

X₂

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

0

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

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

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

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

N

X₁

X₂

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

1

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

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

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

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

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

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

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

N

X₁

X₂

y

0

0

0

0

1

0

1

1

2

1

0

1

3

1

1

0

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

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

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

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

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

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

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

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

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

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

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

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

Ход урока:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В ДНФ:

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

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

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

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

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

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

В КНФ:

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

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

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

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

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

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

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

N

X₁

X₂

X₃

F

Для ДНФ

Для КНФ

0

0

0

0

0

Х₁+х₂+х₃

1

0

0

1

1

_ _

Х₁*х₂*х₃

2

0

1

0

1

_ _

Х₁*х₂*х₃

3

0

1

1

0

_

Х₁+х₂+х₃

4

1

0

0

1

_ _

Х₁*х₂*х₃

5

1

0

1

0

_ _

Х₁+х₂+х₃

6

1

1

0

0

_ _

Х₁+х₂+х₃

7

1

1

1

1

Х₁*х₂*х₃

_ _ _ _ _

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

_ _ _ _ _

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

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

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

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

Решение:

N

X₁

X₂

X₃

F

Для ДНФ

Для КНФ

0

0

0

0

0

Х₁+х₂+х₃

1

0

0

1

1

_ _

Х₁*х₂*х₃

2

0

1

0

1

_ _

Х₁+х₂+х₃

3

0

1

1

0

_

Х₁+х₂+х₃

4

1

0

0

1

_ _

Х₁*х₂*х₃

5

1

0

1

0

_ _

Х₁+х₂+х₃

6

1

1

0

0

_

Х₁*х₂*х₃

7

1

1

1

1

_ _ _

Х₁*х₂*х₃

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

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

_ _ _ _ _ _ _ _

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

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

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

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

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

Ход урока

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

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

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

_ _ _ _ _ _ _

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

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

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

Составить аналитическое выражение в КНФ и в ДНФдля функции от 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

3. Итог урока

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

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

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

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

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

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

Ход урока

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

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

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

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

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

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

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

X₁

X₂

X₃

F

Для ДНФ

0

0

0

0

0

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

_

Х₁*х₂*х₃

4

1

0

0

0

5

1

0

1

1

_

Х₁*х₂*х₃

6

1

1

0

1

_

Х₁*х₂*х₃

7

1

1

1

1

Х₁*х₂*х₃

_ _ _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. Тема урока: "Типовые задачи по преобразованию логических функций"

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

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

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

Ход урока

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

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

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

• Какие следствия из законов вы знаете? 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

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

Упражнение: 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

3. Итог урока

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

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

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

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