Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Ноябрь 2006   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

уроки и методика преподавания информатики для учителей www.thl.narod.ru


Логические функции Логической (булевой) функцией называют функцию F(Х1, Х2, ..., Хn), аргументы которой Х1, Х2, ..., Хn (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1. Таблицу, показывающую, какие значения принимает логическая функция при всех сочетаниях значений ее аргументов, называют таблицей истинности логической функции. Таблица истинности логической функции n аргументов содержит 2n строк, n столбцов значений аргументов и 1 столбец значений функции. Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул. Если логическая функция представлена с помощью дизъюнкций, конъюнкций и инверсий, то такая форма представления называется нормальной. Существует 16 различных логических функций от двух переменных. Таблица 3.1. Логические функции двух переменных Аргументы Логические функции A B F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Пример 3.6. По имеющимся таблицам истинности выразите через базовые логические функции (конъюнкцию, дизъюнкцию и отрицание) следующие функции: а) F9(X, Y) б) F15(X, Y) Из таблицы истинности видно, что F9(X, Y) = (отрицание дизъюнкции). Из таблицы истинности видно, что F15(X, Y) = (отрицание конъюнкции). Задания для самостоятельного выполнения. 3.27. По имеющимся таблицам истинности выразите через базовые логические функции (конъюнкцию, дизъюнкцию и отрицание) следующие функции: а) F3(X, Y); б) F5(X, Y); в) F7(X, Y); г) F10(X, Y); д) F11(X, Y); е) F12(X, Y); ж) F13(X, Y); з) F14(X, Y). 3.28. С помощью электронных таблиц (например, StarCalc) построить таблицы истинности для всех возможных логических функций двух переменных. Логические законы и правила преобразования логических выражений Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных. В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы. 1. Закон двойного отрицания: А = . Двойное отрицание исключает отрицание. 2. Переместительный (коммутативный) закон: — для логического сложения: А  B = B  A; — для логического умножения: A&B = B&A. Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. В обычной алгебре a + b = b + a, a  b = b  a. 3. Сочетательный (ассоциативный) закон: — для логического сложения: (A  B)  C = A  (B  C); — для логического умножения: (A&B)&C = A&(B&C). При одинаковых знаках скобки можно ставить произвольно или вообще опускать. В обычной алгебре: (a + b) + c = a + (b + c) = a + b + c, а  (b  c) = a  (b  c) = a  b  c. 4. Распределительный (дистрибутивный) закон: — для логического сложения: (A  B)&C = (A&C)  (B&C); — для логического умножения: (A&B)  C = (A  C)&(B  C). Определяет правило выноса общего высказывания за скобку. В обычной алгебре: (a + b)  c = a  c + b  c. 5. Закон общей инверсии (законы де Моргана): — для логического сложения = & ; — для логического умножения: =  6. Закон идемпотентности ( от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный): — для логического сложения: 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). Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут. Пример 3.7. Найдите X, если  = В. Воспользуемся законом де Моргана для логического сложения и законом двойного отрицания: ( & )  ( &A) = &(  A) = &1 = = B. Тогда X = . Пример 3.8. Упростите логическое выражение (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& ) Согласно распределительному (дистрибутивному) закону для логического умножения: (C& )  (A& ) = (C  A)&(C  )&(  A)&(  ) Согласно закона исключения третьего: (C  ) = 1 (  A) = 1 Подставляем значения и окончательно получаем: B& & . Задания для самостоятельного выполнения 3.29. Какое тождество записано неверно: 1) X  = 1; 2) X  X  X  X  X  X = 1; 3) X & X & X & X & X = X. 3.30. Определите, каким законам алгебры чисел (сочетательному; переместительному; распределительному; аналога нет) соответствуют следующие логические тождества: а) А  B = B  A; б) (A&B)&C = A&(B&C); в) А  (В&С) = (А  В)&(А  С); г) (A  B)&C = (A&C)  (B&C). 3.31. Логическое выражение называется тождественно-ложным, если оно принимает значения 0 на всех наборах входящих в него простых высказываний. Упростите следующее выражение и покажите, что оно тождественно-ложное. (А&B& )  (A& )  (B&C& ). 3.32. Логическое выражение называется тождественно-истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний. Упростите следующее выражение и покажите, что оно тождественно-истинное. (А&B& )  (A&B&C)  . 3.33. Упростите логические выражения. Правильность упрощения проверьте с помощью таблиц истинности для исходных и полученных логических формул. а) А  ( &В); б) А&(  В); в) (A  B)&(  A)&(  B); г) (1  (A  B))  ((A  C)&1).
В избранное