22.10.2006

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

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

Цели урока:

  1. Обучающие:
    1. Изучить основные законы логики
    2. Научить преобразовывать логические выражения, используя логические законы
    3. Ввести понятие “нормальная форма логической формулы”
    4. Закрепить навыки упрощения логических выражений, используя логические законы
    5. Научить решать логические задачи
    6. Закрепить навыки решения логических задач
  2. Развивающие:
    1. Развивать логическое мышление
    2. Развивать внимание
    3. Развивать память
    4. Развивать речь учащихся
  3. Воспитывающие:
    1. Воспитывать умение слушать учителя и одноклассников
    2. Воспитывать аккуратность ведения тетради
    3. Воспитывать дисциплинированность

Ход урока

Организационный момент

Здравствуйте, ребята. Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Законы логики и правила преобразования логических выражений». Изучив данную тему, вы узнаете, основные законы логики, научитесь упрощать логические выражения, используя логические законы, решать логические задачи

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

Какой у вас получился ответ в домашней задаче? (2)

Откройте свои тетради там, где вы выполняли домашнюю работу, я пройду посмотрю

Объяснение нового материала

Переходим к новой теме.

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

1. Закон двойного отрицания:

А = .

 Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

— для логического сложения:

A V B = B V A

— для логического умножения:

A&B = B&A.

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

 В обычной алгебре   2 + 3 = 3 + 2, 2 ´ 3 = 3 ´ 2.

3. Сочетательный (ассоциативный)  закон:

— для логического сложения:

(A Ú B) Ú C = A Ú (BÚ C);

— для логического умножения:

(A&B)&C = A&(B&C).

 При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

 В обычной алгебре:   (2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4, 5 ´ (6 ´ 7) = 5 ´ (6 ´ 7) = 5 ´ 6 ´ 7.

4. Распределительный (дистрибутивный) закон:

— для логического сложения:

(A Ú B)&C  = (A&C) Ú (B&C);

— для логического умножения:

(A&B) Ú C = (A Ú C)&(B Ú C).

 Определяет правило выноса общего высказывания за скобку.

 В обычной алгебре:   (2 + 3) ´ 4 = 2 ´ 4 + 3 ´4.

5. Закон общей инверсии (законы де Моргана):

— для логического сложения

 = & ;

— для логического умножения:

 =  Ú

6. Закон идемпотентности

— для логического сложения:

A Ú A = A;

— для логического умножения:

A&A = A.

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

— для логического сложения:

A Ú 1 = 1,      A Ú 0 = A;

— для логического умножения:

A&1 = A,     A&0 = 0.

8. Закон противоречия:

A& = 0.

 Невозможно, чтобы противоречащие высказывания были одновременно истинными.

 9. Закон исключения третьего:

A Ú = 1.

10. Закон поглощения:

— для логического сложения:

A Ú (A&B) = A;

— для логического умножения:

A&(A Ú B) = A.

11. Закон исключения (склеивания):

— для логического сложения:

(A&B) Ú ( &B) = B;

— для логического умножения:

(A Ú B)&( Ú B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Û  B) = (BÛ A).
┐(А→В) = А&┐В
┐А&(АÚВ)= ┐А&В
АÚ┐А&В=АÚВ

Формула имеет нормальную форму, если в ней отсут­ствуют знаки эквивалентности, импликации, двойного от­рицания, при этом знаки отрицания находятся только при переменных.

 Пример 1. Найдите X, если Ú = В.

Упростим левую часть равенства. Какими законами воспользуемся? Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

  ( & ) Ú ( &A)

Согласно распределительному закону для логического сложения:     

&( Ú A)

Согласно закону исключения третьего и закона исключения констант:

&1 =

Полученную левую часть приравняем правой:

* = В

Окончательно получим, что  

X =  .

 Пример 2. Упростите логическое выражение (A Ú B Ú C)&

Посмотрите на выражение, посмотрите на законы, что можно сделать?

Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:

(A Ú B Ú C)& = (A Ú B Ú C)&( &B& )

 Согласно распределительному (дистрибутивному) закону для логического сложения:

(A Ú B Ú C)&( &B& ) = (A& ) Ú (B& ) Ú (C& ) Ú (A&B) Ú (B&B) Ú (C&B) Ú (A& ) Ú (B& ) Ú (C& )

Согласно закона противоречия:

 (A& ) = 0; (C& ) = 0

 Согласно закона идемпотентности

(B&B) = B

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

0 Ú (A&B) Ú ( &B) Ú B Ú (C&B) Ú ( &B) Ú (C& ) Ú (A& ) Ú 0

 Согласно закона исключения (склеивания)

(A&B) Ú ( &B) = B
(C&B) Ú ( &B) = B

 Подставляем значения и получаем:

0 Ú B Ú B Ú B Ú (C& ) Ú (A& ) Ú 0

 Согласно закона исключения констант для логического сложения и закона идемпотентности:

  0 Ú B Ú 0 Ú B Ú B = B

 Подставляем значения и получаем:

B Ú (C& ) Ú (A& )

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

Упростить логическую формулу:

(A v В) →(В v С).

2-й час

Сегодня мы продолжаем изучать тему “Законы логики и правила преобразования логических выражений”. Будем упрощать выражения и учиться решать логические задачи

Но для начала проверим как вы выполнили домашнее задание (1 ученик у доски, остальные показывают в тетрадях).

Решение задач

1.Упростить логическое выражение

  1. (АÚ┐А) &В
  2. А& (АÚВ) & (ВÚ┐В)

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

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

Упростить выражение и показать, что оно тождественно – ложное

(А&В&┐В) Ú (А&┐А) Ú (В&С&┐С)

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

Упростить выражение и показать, что оно тождественно – истинное

(А&В&┐С) Ú (А&В&С) Ú┐(АÚВ)

3.Переведите к виду логической формулы вы­сказывание:   «Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра».

Решение. Определим следующие простые высказывания:

П - «пасмурная погода»;
Д -  «идет дождь»;
В - «дует ветер».

Тогда  соответствующее  логическое  выражение  запишется так:

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

4. Задача

В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку «По крайней мере, в одной из этих аудиторий размешается кабинет информатики», а на второй аудитории — табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.

Решение задачи.

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

А = «В первой аудитории находится кабинет информатики»;
В = «Во второй аудитории находится кабинет информатики».

Отрицаний этих высказывании:

А = «В первой аудитории находится кабинет физики»;
В = «Bo второй аудитории находится кабинет физики».

Высказывание, содержащееся на табличке на двери первой аудитории, соответствует логическому выражению:

X = АÚВ.

Высказывание, содержащееся на табличке на двери вто­рой аудитории, соответствует логическому выражению:

Y = А.

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

(X&Y) v(X& Y) = 1.

 Подставим вместо X и Y соответствующие формулы:

(X &Y) v (X & Y) = ((А vB) &A)v ((A v B) & А).

 Упростим сначала первое слагаемое. В соответствии с законом дистрибутивности умножения относительно сложения:

((А vB) &A) = A&A v B&A

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

A&A v B&A = 0 v В&А

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

(A v B) & А = А&В&А = А&А&В

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

А&А&В = 0&В = 0

В результате получаем:

(0 v В & A) v 0 = В& А.

Для того чтобы выполнялось равенство  В & А = 1, В и А должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

5. Упростить логические выражения. Правильность упрощения логических  выражений проверить с помощью таблиц истинности для исходных и полученных логических формул.

  1. АÚ (┐А&В)
  2. А& (┐АÚВ)
  3. (АÚВ) & (┐ВÚА) & (┐СÚВ)

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

В процессе составления расписания уроков учителя высказали свои пожелания. Учитель математики, высказал пожелание про­водить первый или второй урок, учитель информатики — первый или третий, а учитель физики  второй или третий урок. Сколько существует возможных вариантов расписания и каковы они?

3-й час

Проверим, как вы выполнили домашнюю работу.

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

1. Задача

Кто из учеников А, В, С и D играет, а кто не играет в шахматы, если известно следующее:

  • а) если А или В играет, то С не играет;
  • б) если В не играет, то играют С и D;
  • в)  С играет

Решение. Определим следующие простые высказывания:

  • А — «ученик А играет в шахматы»;
  • В — «ученик В играет в шахматы»;
  • С — «ученик С играет в шахматы»;
  • D — «ученик D играет в шахматы».

Запишем высказывания:

  • а)  (A v В) → С;
  • б)  В → С & D;
  • в)  С.

Запишем произведение указанных сложных высказываний:

((A v В) → С) & (В → С & D) & С.

Упростим эту формулу:

((A v В) → С) & (В → С & D) & С = ((А v В) v С) & (В v С & D) & С = (А & В) v С) & (В v С & D) & C = A & B & C & D =1.

Отсюда А = 0, В = 1, С = 1, D = 1.

Ответ: в шахматы играют ученики В,С и D, а ученик А не играет.