Основы логики
Употребляйте с пользой время.
Учиться надо по системе.
Сперва хочу вам в долг вменить
На курсы логики ходить.
Ваш ум,не тронутый доныне,
На них приучат к дисциплине,
Чтоб взял он направленья ось,
Не разбредаясь вкривь и вкось.
Что вы привыкли делать дома
Единым махом наугад,
Как люди пьют или едят,
Вам расчленят на три приема
И на субъект и предикат.
В мозгах как и в мануфактуре,
Есть ниточки и узелки.
Посылка не по той фигуре
Грозит запутать челноки.
(Гете "Фауст")
План
1.Литература.
W145 1.В.И.Лобанов.Инженерные методы разработки цифровых уст-
4/231(ЦПТБ) ройств - М.:1977.
2. Информационный листок N% 54-87 В.И.Лобанов "Метод бу-
левых функций от большого числа переменных с помощью
карт Карно".Московской областной территориальный центр
научно-технической информации и пропаганды. 1987 (ТД 87-18-15).
3.В.И.Кириллов,А.А.Старченко.Логика - М.:1995.
4.В.А.Светлов.Практическая логика - СПб.:1997.
5.Б.В.Григорьев.Классическая логика - М.:1996.
6.Г.Л.Бузук.Логика и компьютер - М.:1995.
7.Л.Кэрролл.Логическая игра - М.:1991.
8.К.К.Жоль.Логика в лицах и символах - М.:1993.
9.А.Гжегорчик.Популярная логика - М.:1979.
10.О.В.Суворов.Основы логики для средней школы. - М.:Ак-
вариум,1997.
2.Предмет логики.История становления логики как науки.
3.Основные законы логики.
4.16 функций логики.
5.Старосте подготовить список группы на ПК в Lexicon.
6.Дом.задание на листах(лучше в тонкой тетрадке) в клеточ-
ку.Конспект в клетч.тетради(48 листов).
1.Логика как наука.Основные законы алгебры логики.
Введение.
Логика - наука о мышлении,точнее о закономерностях в связях и
развитии мыслей.
Первое упоминание логики встречается в китайской "Книге пере-
мен"(VIII в до н.э.).В Древней Греции она начала разрабатываться в VI
в до н.э.Немного позже логика возникла в Индии.Первоначально логика
служила юриспруденции(воровство-двигатель прогресса) и ораторскому ис-
кусству.Еще одним стимулом создания науки логики стали запросы матема-
тики,где требовались строгие доказательства.В Древней Греции логику
разрабатывали Парменид (VIв. до н.э.),Демокрит,Сократ,Платон(V в до
н.э.) и Аристотель(IV в до н.э.).
Аристотель,внук легендарного врача Асклепия,родился в г.Стаги-
ра(второе имя - Стагирит) в 384 г. до н.э.Обучался в академии Плато-
на,был дружен с царем Филиппом,обучал логике его сына Александра Маке-
донского.Впервые ввел в логику законы и правила,основал силлогисти-
ку,т.е.создал логику.Смерть Аристотеля датируется 322 г до н.э.(яд?).
Принципы современной математической логики предвосхитил в своей
работе "Об искусстве комбинаторики"(1666) великий немецкий философ,ма-
тематик,физик и языковед Готфрид Вильгельм Лейбниц(1646-1716).
Великий русский и швейцарский ученый Леонард Эйлер(1707-1783) с
1727г. по 1741г. работал в России.С 1766г. был избран академиком Пе-
тербургской АН.Ученый необычайной широты интересов.Автор свыше 800 ра-
бот по математике,физике,небесной механике,оптике,баллистике,кораб-
лестроению,теории музыки.Предложил так называемые круги Эйлера,ставшие
основой формальной силлогистики.
Однако основоположником математической логики считается Джордж
Буль(1815-1864),английский математик,отец всемирно известной писатель-
ницы Этель Лилиан Войнич(роман "Овод").
Лекции не научат вас логически мыслить,поскольку каждый человек
обладает этим даром от природы.Человечество достигло современных вер-
шин цивилизации не благодаря,а скорее вопреки формальной логике.Но
формальная логика поможет вам справиться с обработкой большого объема
информации при анализе и синтезе силлогизмов,при решении логических
уравнений,при синтезе микропрограммных автоматов.В настоящее время
значение математической логики сильно возросло в связи с насущной не-
обходимостью создания искусственного интеллекта.Пока не будут решены
проблемы силлогистики,искусственный интеллект останется пустым звуком.
Силлогистика - фундамент искусственного интеллекта.
Предлагая свои методы решения многих проблем логики,в том числе в
области силлогистики,решения логических уравнений и минимизации логи-
ческих функций, автор не претендует на истину в последней инстан-
ции,тем более,что к решению этих проблем вплотную подошли русские ло-
гики Кулик Б.А.[9],Светлов В.А.[18],Брусенцов Н.П.[5].
1.1.Основные законы алгебры логики.
В алгебре логики переменные могут принимать только 2 значения:
0 или 1.
Табл.1.1 Табл.1.2
------------T------------¬ -----------T---------¬
¦Аргументы ¦ Функции ¦ ¦Аргументы ¦ Функция¦
+-----------+------T-----+ +----------+---------+
¦ ¦ И ¦ ИЛИ¦ ¦ ¦ НЕ ¦
¦ х1 х2 +------+-----+ ¦ х +---------+
¦ ¦ у1¦ у2¦ ¦ ¦ у3 ¦
+-----------+------+-----+ +----------+---------+
¦ 0 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦
¦ 0 1 ¦ 0 ¦ 1 ¦ +----------+---------+
¦ 1 0 ¦ 0 ¦ 1 ¦ ¦ 1 ¦ 0 ¦
¦ 1 1 ¦ 1 ¦ 1 ¦ L----------+---------+
+-----------+------+------
И -логическое умножение,конъюкция.
ИЛИ -логическое сложение,дизъюнкция.
НЕ -отрицание,инверсия.
Графическое и аналитическое представление основных логических
функций приведено на рисунке 1.1.
------¬ ------¬ __
X1--+ & ¦ X1--+ 1 о--У3=Х1
Х2--+ +--У1=Х1*Х2 L------
L------
------¬
X1--+ 1 ¦
X2--+ +--Y2=X1+X2 Рис.1.1
L------
У1=Х1*Х2=Х1&X2=Х1Х2=X1 ^ X2
У2=Х1+Х2=Х1VХ2
_
У3=Х
Далее в качестве знака отрицания вместо "крышки" будет использо-
ваться апостроф.
Для n переменных в двоичной логике имеется 2^2^n функций.Полный
набор логических функций от 2-х переменных представлен в табл.1.3.
Табл.1.3
-----T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ xy ¦z0 ¦z1 ¦z2 ¦z3 ¦z4 ¦z5 ¦z6 ¦z7 ¦z8 ¦z9 ¦z10¦z11¦z12¦z13¦z14¦z15¦
+----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 00 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 01 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 10 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 11 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
L----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Некоторые из этих функций получили специальные названия:
z0 = 0 - тождественный нуль;
z1 = xy - конъюнкция;
z6 = xy'+x'y - неравнозначность,сумма по модулю 2;
z7 = x+y - дизъюнкция;
z8 = x'y' = (x+y)' - функция Вебба(стрелка Пирса);
z9 = x'y'+xy - равнозначность;
z13= x'+y= x -> y - импликация,а также Axy;
z14= x'+y' = (xy)' - функция Шеффера,а также Exy;
z15= 1 - тождественная 1,а также Ixy(8).
1.2.Основные законы алгебры Буля.
1. Комплементарность.
a*a'=0; a+a'=1
2. Идемпотентный закон.
а*а=а; а+а=а
3. Переместительный закон.
а+в=в+а; ав=ва
4. Сочетательный закон.
(а+в)+с=а+(в+с); (ав)*с=а*(вс)
5. Закон поглощения.
а+ав=а(1+в)=а; а(а+в)=а+ав=а
6. Распределительный закон.
а(в+с)=ав+ас; (а+в)(а+с)=а+вс
/* (а+в)(а+с)=а*а+ав+ас+вс=(а+ав+ас)+вс=
=а(1+в+с)+вс=а+вс */
7. Закон склеивания
ав+ав'=а(в+в')=а;
(а+в)(а+в')=а+ав+ав'+вв'=а+а(в+в)+0=
=а+а*1=а+а=а
8.Правила де Mоргана.
____ ____
_ _ _ _
а+в = а*в; а*в = а*в
_________ __________
_ _ _ _ _ _
/*а+в+...+z = а*в...*z; а*в*...*z = а+в+...+z */
Заучивать все логические законы и запоминать их названия нет ни-
какого смысла,тем более,что на практике используются 2-3 из них(законы
поглощения и склеивания,правила Де Моргана).Значительно важнее осмыс-
лить эти законы и научиться применять.
С помощью правил де Моргана легко реализуются логические схемы на
базе интегральных схем(ИС) так называемого функционально полного бази-
са(ФПБ).ФПБ характерен тем,что на его основе можно построить любую
сколь угодно сложную схему,в том числе и самую сложную вычислительную
машину без применения других ИС.К ФПБ относятся ИС типа И-НЕ,а также
ИЛИ-НЕ.Таким образом,на очень простом элементе типа И-НЕ может быть
построена,например,сложная система управления ракетой.Только в этой
системе управления простые элементы И-НЕ сгруппированы в большие ин-
тегральне схемы(БИС),которые выполняют функции процессора,памяти и то-
му подобных сложных устройств.
Пусть нам необходимо построить схему,реализующую функцию
y = x1x2 + x3x4.Используя формулу де Моргана,получим следующее соотно-
шение:
y = x1x2 + x3x4 = ((x1x2)'(x3x4)')'.
Таким образом,мы выразили исходную функцию с помощью одних только
элементов И-НЕ.Схема реализации заданной функции представлена на ри-
сунке.
------¬
X1--+ & ¦ (x1x2)'
Х2--+ о-------¬ ------¬
L------ L-------+ & ¦ y=((x1x2)'(x3x4)')'=x1x2+x3x4
--------+ о--
------¬ ¦ L------
X3--+ & ¦ ¦
Х4--+ о--------
L------ (x3x4)'
Синтез релейных схем выполняется также на основе алгебры логики.
3.Задача.
Задержаны подозреваемые в преступлении Браун,Джон и Смит.Один из
них говорит правду,другой - полуправду,третий - ложь.Приведем их пока-
зания.
Браун:"Я совершил это,Джон не виноват."
Джон:"Браун не виноват,преступник - Смит."
Смит:"Я не виноват,виноват Браун."
Найти преступника,если известно,что он один.
Решение.
Введем обозначения:
B - виноват Браун;
C - виноват Смит;
D - виноват Джон.
Тогда условие задачи будет выражено двумя уравнениями:
1)BD'+B'C+BC' = 1(показания подозреваемых,одно из них истинно);
2)B'C'+B'D'+C'D' = 1(преступник единственный).
M = (BD'+B'C+BC')(B'C'+B'D'+C'D') = B'CD'+BC'D' = 1.
BC'D' отпадает,т.к. иначе Браун и Смит оба говорят правду.Следо-
вательно,истинно B'CD',т.е. преступник - Смит,он еще и лжец.Джон гово-
рит правду,Браун - полуправду.Кстати,отсеять BC'D' можно было на пер-
вом этапе,поскольку из условий задачи следует BD'+BC' = 0,поэтому
M = B'C(B'C'+B'D'+C'D') = B'CD'.
4.Задача.
Если в экспедицию поедет Арбузов,то поедут и Брюквин с Вишневс-
ким.Если поедут Арбузов с Вишневским,то поедет и Брюквин.Кто отправит-
ся в экспедицию?
Решение.
A - поедет Арбузов.
B - поедет Брюквин.
W - поедет Вишневский.
1)A -> (B+W);
2)AW -> B.
M = (A'+B+W)(A'+W'+B) = A'+B = A -> B,т.е. если поедет Арбузов,то
поедет и Брюквин.