Урок 4 Информатика 11 класс

Тема: Логические функции.

 

Цель урока: Изучить логические функции двух аргументов. Построить таблицы истинности всех логические функции двух аргументов, используя электронные таблицы Excel.  

 

Любое логическое выражение можно рассматривать как логическую функцию F(X₁, X₂, . . . X_n), аргументами которой являются логические переменные X₁, X₂, . . . X_n . Сама функция и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0).

Каждая логическая функция двух аргументов имеет четыре возможных значения. Каждое значение функции несёт один бит информации, так как может быть либо 0, либо 1. Следовательно каждая функция несёт 4 бита информации и можно определить, какое количество различных логических функций двух аргументов может существовать:

 

                                          N = 2^I = 2⁴ = 16.

Таким образом, существует 16 различных логических функций  двух аргументов, каждая из которых задаётся собственной таблицей истинности. 

 

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

 

Аргументы		Логические функции
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

 

Легко заметить, что логическая функция

F₂ является функцией логического умножения,

F₈ – функция логического сложения,

F₁₃ – функция логического отрицания для аргумента А,

F₁₁ – функция логического отрицания для аргумента В.

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

 

Логическая операция ИМПЛИКАЦИЯ (логическое следование):

 

·        В естественном языке соответствует обороту если . . . , то . . .

·        Обозначение   (→ ) .

Логическое следование  (импликация) образуется соединением двух высказываний в одно с помощью оборота речи  «если . . . , то . . .».

Логическая операция импликации «если А, то В» обозначается А → В и выражается с помощью логической функции F, которая задаётся соответствующей таблицей истинности.

 

А	В	F = A → B
0	0	1
0	1	1
1	0	0
1	1	1

 

 

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

 

 

 

 

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, так как истинны и первое высказывание (посылка) и второе высказывание (вывод).

Высказывание «Если число делится на 10, то оно делится на три» ложно, так как из истинной посылки делается ложный вывод.

Однако операция логического следования несколько отличается от обычного понимания слова «следует». Если первое высказывание (посылка) ложно, то вне зависимости от истинности или ложности второго высказывания (вывод) составное высказывание истинно. Это можно понимать таким образом, что из неверной посылки может следовать что угодно.

В алгебре логики все логические функции могут быть выражены путём логических преобразований через три базовые логические функции:

Ø  Логическое умножение

Ø  Логическое сложение

Ø  Логическое отрицание. 

 

Пример «Безопасность движения»

«Если поезд прибывает на данный путь, то подаётся сигнал, что путь закрыт».

 А = «Поезд прибывает на данный путь»

В = «Подаётся сигнал, что путь закрыт»

Рассматриваемое сложное высказывание истинно (1), если

1)      Поезд прибывает (1), сигнал «закрыт» (1);

2)      Поезд не прибывает (0), сигнал «свободен» (0); Если поезд не прибывает, безопасен любой сигнал.

3)      Поезд не прибывает (0), сигнал «закрыт» (1). Если поезд не прибывает, безопасен любой сигнал.

Рассматриваемое сложное высказывание «ложно» (0), безопасность не обеспечивается только в том случае, если поезд прибывает (1), а сигнал «не закрыт (свободен)» (0). 

 

А	В	F = A → B
0	0	1
0	1	1
1	0	0
1	1	1

Практическое задание «Функция импликации».

Выразить функцию импликации F₁₄ через базовые логические функции. Доказать методом   _ сравнения таблиц истинности, что функция импликации равносильна логическому выражению A V B   Построить таблицу истинности импликации в электронных таблицах Excel.

 

A	B	_ A	_ A V B
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

 

                                                                                                                               _

 Таблицы истинности функции импликации F₁₄ и логического выражения A V B совпадают, что и требовалось доказать.

 

Получение таблицы истинности функции импликации в электронных таблицах Excel.

1.              В электронных таблицах создать заготовку таблицы истинности функции импликации: создать заголовки и ввести в столбцы А и В значения логических аргументов.

2.              В столбце С выразить логическую функцию  F₁₄ = ⌐A V B через логические функции электронных таблиц Microsoft Excel    

   

                             

 

 

 

 

Логическая операция ЭКВИВАЛЕНТНОСТЬ (логическое равенство, равнозначность):

 

·         В естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;

·         Обозначения ↔ ,  ~  .

Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи « . . . тогда и только тогда, когда . . . ».

Логическая операция эквивалентности «А эквивалентно В» обозначается  А ~ В и выражается с помощью логической функции F, которая задаётся соответствующей таблицей истинности:

 

А	В	А ~ В
0	0	1
0	1	0
1	0	0
1	1	1

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

 

 

 

 

 

 

Рассмотрим, например, два высказывания:

А = «Компьютер может производить вычисления» 

В = «Компьютер включён»

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

«Компьютер может производить вычисления тогда и только тогда, когда компьютер включён» 

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включён»

 

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

«Компьютер  может производить вычисления тогда и только тогда, когда компьютер не включён»

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включён» 

 

Практическое задание. Выразить функцию эквивалентности F₁₀ через базовые логические функции. 1) Доказать методом сравнения таблиц истинности, что функция эквивалентности равносильна  

                                              _     _

логическому выражению (A & B) V (A & B).

2) Построить таблицу истинности функции  эквивалентности в электронных таблицах Excel. 

                                                                                                  _     _

Построим таблицу истинности логического выражения (A & B) V (A & B).

 

A	B	_ A	_ B	_      _ A & B	A & B	_     _ (A & B) V (A & B)
0	0	1	1	1	0	1
0	1	1	0	0	0	0
1	0	0	1	0	0	0
1	1	0	0	0	1	1

                                                                                                                                  _     _

Таблицы истинности функции эквивалентности и логического выражения (A & B) V (A & B) совпадают, что и требовалось доказать.  

 

Получение таблицы истинности функции эквивалентности в электронных таблицах Excel.

1. В электронных таблицах создать заготовку таблицы истинности функции эквивалентности: создать заголовки и ввести в столбцы А и В значения логических аргументов. 

                                                                                              _      _

2. В столбце С выразить логическую функцию  F₁₀ = (A & B) V (A & B) через логические функции электронных таблиц Microsoft Excel. 

 

 

    

 

 

 

Логическая функция	Название
F1 (X1, X2 ) = 0	Константа 0
F2 (X1, X2 ) = X1 · X2	Конъюнкция, логическое умножение
_______ F3 (X1, X2 ) = X1 → X2	Запрет по X1, отрицание импликации
F4(X1, X2 ) = X1	Переменная X1
_______    F5 (X1, X2 ) = X2 → X1	Запрет по X2, отрицание импликации
F6(X1, X2 ) = X2	Переменная X2
F7 (X1, X2 ) = X1  X2	Сложение по модулю два, логическая неравнозначность
F8 (X1, X2 ) = X1 + X2	Дизъюнкция (логическое сложение)
F9 (X1, X2 ) =X1 ↓ X2	_______          Отрицание дизъюнкции, стрелка Пирса (Х1 + Х2)
F10 (X1, X2 ) = X1 ↔ X2	Эквивалентность (равнозначность)
__ F11 (X1, X2 ) = X2	Отрицание, инверсия Х2
F12 (X1, X2 ) = Х2 → Х1	Импликация, Х2 → Х1
__ F13 (X1, X2 ) = Х1	Отрицание, инверсия Х1
F14 (X1, X2 ) = Х1 → Х2	Импликация, Х1 → Х2
F15 (X1, X2 ) = Х1 | Х2	Штрих Шеффера, отрицание конъюнкции (Х1 · Х2)
F16 (X1, X2 ) = 1	Константа 1

 

Контрольные вопросы:

1. Какое количество логических функций двух аргументов существует и почему? 
2. Какие названия логических функций двух аргументов вы знаете?
3. Какое количество логических функций трёх аргументов существует и почему? 

 

Задания: Доказать с использованием таблиц истинности правильность выражения логических функций  через базовые логические функции (конъюнкцию, дизъюнкцию и отрицание):

 

_ F1(A,B) = A & A	_  F5(A,B) = A & B	_____ F9(A,B) = A V B	_ F13(A,B) = A
F2(A,B) = A & B	F6(A,B) = B	_      _ F10(A,B) = (A & B) V (A & B)	_   F14(A,B) = A V B
_ F3(A,B) = A & B	_                       _ F7(A,B) = (A & B) V (A & B)	_ F11(A,B) = B	_____  F15(A,B) = A & B
F4(A,B) = A	F8(A,B) = A V B	_  F12(A,B) =  B V A	_ F16(A,B) = A V A

 

 

В электронных таблицах Excel построить таблицы истинности всех логических функций двух переменных.