Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Методическое пособие по основам математической логики

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

Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

  • Информатика

Поделитесь материалом с коллегами:

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

Цели урока:

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

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

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

Ход урока

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

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

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

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

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

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

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

Пример: Логическая функция F12х3) принимает значения, равные 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



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

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

  1. Итог урока

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

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

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

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

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

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

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

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

Цели урока:

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

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

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

Ход урока



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

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

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

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

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

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

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

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

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

В-1: F123) =1 на наборах 1,2,5,

В-2: F123) =1 на наборах 0,3,5,

В-3: F123) =1 на наборах 2,5,7

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

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

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

N

x

Y

0

0

1

1

1

0



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

    N

    X1

    X2

    y

    0

    0

    0

    0

    1

    0

    1

    0

    2

    1

    0

    0

    3

    1

    1

    1

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

N

X1

X2

y

0

0

0

0

1

0

1

1

2

1

0

1

3

1

1

1



  1. Итог урока

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

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

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

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

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

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




Цели урока:

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

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

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

Ход урока



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

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

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

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

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

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


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


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

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

Обозначение: F = x1→x2 или F = x1 + x2.

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

N

X1

X2

F

0

0

0

1

1

0

1

1

2

1

0

0

3

1

1

1




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

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

Обозначается: у = х12hello_html_2e1d231c.gif = х12 = х1↓ х2.

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

N

X1

X2

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

0




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

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

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

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

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

N

X1

X2

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

0




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

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

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

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


N

X1

X2

y

0

0

0

1

1

0

1

0

2

1

0

0

3

1

1

1



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

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

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

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

Обозначение: у = х1 ♀ х2

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

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

N

X1

X2

y

0

0

0

0

1

0

1

1

2

1

0

1

3

1

1

0




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


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


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

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

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

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


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


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

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



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

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

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


Ход урока:



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

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

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

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

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



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


Х123

1

0

0

1

1

_ _

Х123


2

0

1

0

1

_ _

Х123


3

0

1

1

0


_

Х123

4

1

0

0

1

_ _

Х123


5

1

0

1

0


_ _

Х123

6

1

1

0

0


_ _

Х123

7

1

1

1

1


Х123


_ _ _ _ _

F(ДНФ) = Х123+ Х123+ Х123+ Х123

_ _ _ _ _

F(КНФ) =( Х123 )( Х123 )( Х123 )( Х123 )


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


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

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

Решение:

N

X1

X2

X3

F

Для ДНФ

Для КНФ

0

0

0

0

0


Х123

1

0

0

1

1

_ _

Х123


2

0

1

0

1


_ _

Х123

3

0

1

1

0


_

Х123

4

1

0

0

1

_ _

Х123


5

1

0

1

0


_ _

Х123

6

1

1

0

0

_

Х123


7

1

1

1

1



_ _ _

Х123


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

Х123123+ Х123

_ _ _ _ _ _ _ _

F(КНФ) = (Х123 )( Х123 )( Х123 )( Х123)( Х123) 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

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

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

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

  1. Итог урока

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

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

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

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

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

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

Ход урока



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

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

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



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

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

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


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

_

Х123

4

1

0

0

0


5

1

0

1

1

_

Х123

6

1

1

0

1

_

Х123

7

1

1

1

1


Х123



_ _ _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

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


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

  1. Итог урока

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

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


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


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




Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

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

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy

Автор
Дата добавления 09.11.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров206
Номер материала ДВ-137820
Получить свидетельство о публикации

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.

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

Список всех тестов можно посмотреть тут - https://infourok.ru/tests


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