Geum.ru

Ионова Светлана Георгиевна, учитель информатики и икт г. Биробиджан, 2011 год Ионова С. Г. Основы логики на урок

Вид материалаУрок

Содержание


Алгебра логики. Высказывания.
Высказывательная форма
Логические связки
Алгебра высказываний
А = «Два умножить на два равно четырем». В
Объединение двух (или нескольких) высказываний в одно с помощью союза «и» называется
Таблица истинности функции логического умножения
Таблица истинности функции логического сложения
Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.
А в алгебре логики принято обозначать |А.
Таблица истинности функции ИМПЛИКАЦИЯ
Таблица истинности функции эквиваленции
Логические переменные и таблицы истинности
Алгоритм построения таблицы истинности
1. Найдите значения логических выражений
2. Даны два простых высказывания
Логические законы и правила преобразования логических выражений
1. Закон тождества.
3. Закон исключенного третьего.
4. Закон двойного отрицания.
...
Полное содержание
Подобный материал:

муниципальное общеобразовательное учреждение

«Средняя общеобразовательная школа №6»


Основы логики

на укорах информатики


Ионова Светлана Георгиевна,

учитель информатики и ИКТ

г. Биробиджан, 2011 год

Ионова С.Г. Основы логики на уроках информатики. Брошюра, в помощь учителю информатики, г.Биробиджан, 2011, 18 с.

Содержание:

Алгебра логики. Высказывания. 4

Алгебра высказываний 8

Логические переменные и таблицы истинности 13

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

Литература: 20

Алгебра логики. Высказывания.



Алгебра логики возникла в середине XIX века в трудах Джорджа Буля.

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


Джордж Буль (основоположник)

Формальной логикой принято называть античную логику, основанную Аристотелем. Логика изучает формы мышления с точки зрения их структуры, законы и правила получения некоторого знания. Формами мышления являются: понятие, суждение, умазаключение.

Понятие – форма мышления, отражающая существенные свойства предмета или класса однородных предметов. Характеризуется содержанием и объёмом. Содержание понятия – те признаки предмета, которые позволяют отличить предмет от остальных. Объём понятия – множество предметов, каждому из которых принадлежат эти призднаки.

Суждение – форма мышления, в которой что-либо утверждается о наличии предмета, его свойствах и действиях. Характеризуется содержанием и формой. Содержанием суждения является его смысл. Форма – способ построения. Суждения бывают истинными и ложными.

Умозаключение – форма мышления, в которой из одного или нескольких суждений на основании определённых правил вывода получается новое суждение.

Высказывание — это некоторое предложение, которое может быть истинно (верно) или ложно.

«6 — четное число»

«Рим — столица Франции»

Высказываниями не являются: «Ученик десятого класса»
«Информатика — интересный предмет»

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

Логические связки

"не",   "и",   "или",  "если... , то",   "тогда и только тогда"

Высказывания бывают Составные или Элементарные

«Петров — врач»,
«Петров — шахматист»

«Петров — врач и шахматист»

«Петров — врач или шахматист»

«Тимур поедет летом на море» - A
«Тимур летом отправится в горы» - B
«Тимур летом побывает и на море,  и в горах» -A и B

Здесь   "и"  — логическая связка.  
А,   В   — логические переменные, которые могут принимать только два значения —   "истина"   или   "ложь", обозначаемые, соответственно,   "1"  и   "0".

Задание.
Установите, какие из следующих предложений являются логическими высказываниями, а какие — нет (объясните почему):

а) “Солнце есть спутник Земли”;
б) “2+3+4”;
в) “сегодня отличная погода”;
г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов”;
д) “Санкт-Петербург расположен на Неве”;
е) “музыка Баха слишком сложна”;
ж) “первая космическая скорость равна 7.8 км/сек”;
з) “железо — металл”;

Определите значения истинности высказываний:
а) “наличия аттестата о среднем образовании достаточно для поступления в институт”;
б) “наличие аттестата о среднем образовании необходимо для поступления в институт”;
в) “если целое число делится на 6, то оно делится на 3”;
г) “подобие треугольников является необходимым условием их равенства”;
д) “подобие треугольников является необходимым и достаточным условием их равенства”;
е) “треугольники подобны только в случае их равенства”;


Сформулируйте отрицания следующих высказываний или высказывательных форм:
а) “Эльбрус — высочайшая горная вершина Европы”;
б) “2>=5”;
в) “10<7”;
г) “все натуральные числа целые”;
д) “через любые три точки на плоскости можно провести окружность”;
е) “теннисист Кафельников не проиграл финальную игру”.

Алгебра высказываний



Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание.
  • В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые прописными буквами латинского алфавита. Рассмотрим два простых высказывания:

А = «Два умножить на два равно четырем».

В = «Два умножить на два равно пяти».
  • Высказывания могут быть истинными или ложными.
  • Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).
  • В алгебре высказываний над высказываниями можно производить определенные логические операции, в результате которых получаются новые, составные высказывания.
  • Для образования новых высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».

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

Пример: Какие из приведенных ниже высказываний будут истинными?

(1) «2 • 2 = 5 и 3 • 3 = 10»,

(2) «2 • 2 = 5 и 3 • 3 = 9»,

(3) «2 • 2 = 4 и 3 • 3 = 10»,

(4) «2 • 2 = 4 и 3 • 3 = 9».
  • В естественном языке конъюнкция соответствует союзу и
  • В языках программирования обозначается and
  • Операцию логического умножения (конъюнкцию) принято обозначать значком «&» либо «». Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:
  • F = А&В.

Таблица истинности функции логического умножения

А
В
F =А&В

0
0
0

0
1
0

1
0
0

1
1
1


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

Пример: Какие из приведенных ниже высказываний будут истинными?

(1) «2 • 2 = 5 или 3 • 3 = 10»,

(2) «2 • 2 = 5 или 3 • 3 = 9»,

(3) «2 • 2 = 4 или 3 • 3 = 10»,

(4) «2 • 2 = 4 или 3 • 3 = 9».

  • В естественном языке дизъюнкция соответствует союзу или
  • В языках программирования обозначается or
  • Операцию логического сложения (дизъюнкцию) принято обозначать либо значком «v», либо знаком сложения «+». Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний:
  • F = A v В.

Таблица истинности функции логического сложения

А
В
F =А v В

0
0
0

0
1
1

1
0
1

1
1
1


Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.
  • Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным.
  • В естественном языке инверсия соответствует частице не
  • В языках программирования обозначается not
  • Пусть А = «Два умножить на два равно четырем» — истинное высказывание, тогда высказывание F = «Два умножить на два не равно четырем», образованное с помощью операции логического отрицания, — ложно.
  • Операцию логического отрицания (инверсию) над логическим высказыванием А в алгебре логики принято обозначать |А.
  • Образуем высказывание F, являющееся логическим отрицанием |А:

F =|А.


Таблица истинности функции логического отрицания


А
F =А

0
1

1
0



  • Составить составное высказывание, содержащее операции логического умножения, сложения и отрицания. Определить его истинность.
  • А=«2*2=5» В=«2*2=4»
  • F=(AVB) & (AVB)
  • F=(0V1) &(1V0)=1&1=1

Логическая операция ИМПЛИКАЦИЯ (логическое следование)
  • в естественном языке соответствует обороту если ..., то ...;
  • обозначение => .
  • Импликация — это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.


Таблица истинности функции ИМПЛИКАЦИЯ

А
В
А => В

0
0
1

0
1
1

1
0
0

1
1
1

Логическая операция ЭКВИВАЛЕНЦИЯ (равнозначность)
  • в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;
  • обозначения <=>, ~
  • Эквиваленция — это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны


Таблица истинности функции эквиваленции:

А
В
А <=> В

0
0
1

0
1
0

1
0
0

1
1
1


Логические операции имеют следующий приоритет
  • действия в скобках,
  • инверсия,
  • конъюнкция &,
  • дизъюнкция v,
  • импликация =>,
  • эквиваленция <=>.

Логические переменные и таблицы истинности



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

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

Алгоритм построения таблицы истинности:

1) подсчитать количество переменных п в логическом выражении;

2) определить число строк в таблице, которое равно т = 2n;

3) подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице,

которое равно количеству переменных плюс количество операций;

4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;

5) заполнить столбцы входных переменных наборами значений;

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


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


а) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

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

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


Например: Для формулы A&(BvB&C) построить таблицу истинности алгебраически.

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2 3 =8.

Количество логических операций в формуле 5, следовательно, количество столбцов в таблице истинности должно быть 3 + 5 = 8.


A
B
C
B
C
B&C
B (B&C)
A&(B B&C)

0
0
0
1
1
1
1
0

0
0
1
1
0
0
0
0

0
1
0
0
1
0
1
0

0
1
1
0
0
0
1
0

1
0
0
1
1
1
1
1

1
0
1
1
0
0
0
0

1
1
0
0
1
0
1
1

1
1
1
0
0
0
1
1


Логической функцией называют функцию F(X1, Х2, ..., Хn), аргументы которой X1, Х2, ..., Хn (логические переменные) и сама функция (логическая переменная) принимают значения О или 1.


Существуют 16 различных логических функций от двух переменных.


аргументы
Логические функции

А
В
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


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

F2 функция логического умножения

F8 функция логического сложения

F13 функция логического отрицания аргумента А

F11 функция логического отрицания аргумента В

F14 функция логической операции импликация

F10 функция логической операции эквиваленция

По имеющимся таблицам истинности выразите через базовые логические функции (конъюнкцию, дизъюнкцию и отрицание) следующие функции:

а) F9(X, У);

б) F15(X, У).

Из таблицы истинности видно, что F9(X, Y) = F8(X,Y) (отрицание дизъюнкции).

Из таблицы истинности видно, что F15(X, Y) = F2(X,Y) (отрицание конъюнкции).

1. Найдите значения логических выражений:

а) (lvl)v(lvO);

б) ((lvO)vl)vl;

в) (Ovl)v(lvO);

г) (0&1)&1;

д) 1&(1&1)&1;

е) ((lvO)&(l&l))&(Ovl);

ж) ((l&0)v(l&0))vl;

з) ((l&l)vO)&(Ovl);

и) ((0&0)vO)&(lvl).

2. Даны два простых высказывания:

А = {2 • 2 = 4},

В = {2 • 2 = 5}.

Какие из составных высказываний истинны:

а)не А; б)не В; в)А&В; г)AvB;

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



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

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

1. Закон тождества.

Всякое высказывание тождественно самому себе:
  • А=А

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

Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:
  • А&A=0

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

Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:
  • AvA = 1

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

Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:
  • А=А

5. Законы де Моргана.
  • АvB=A&B



  • A&B = АvB

6. Закон коммутативности.

В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:
  • АvB= BvА
  • A&B=B&А

7. Закон ассоциативности.

Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
  • ( АvB)vC= Аv(BvC)
  • ( A&B)&C= A&(B&C)

8. Закон дистрибутивности
  • ( А&B)v (А&C) = А& (BvC)
  • ( А v B) & (А v C) = Аv (B& C)



Литература:





  1. Семакин И.Г., Залогова Л.А., Русаков С.В., Шестопалова Л.В. Информатика и ИКТ. Базовый курс. 7-9, М. Лаборатория базовых знаний, 2006.
  2. Винер Н, Кибернетика м, 1983.
  3. Кушниренко А.Г., Лебедев Г.В., Скворень Р.А.Основы информатики и вычислительной техники.М. Прорсвещение, 2006.
  4. Могилёв А.В., Пак Н.И., Хеннер Е.К. Информатика, М. Академия, 2003.
  5. Угринович Н.Д. Информатика и ИКТ. М. Лаборатория базовых знаний, 2006.