Алгебра Логики
Употребляйте с пользой время.
Учиться надо по системе.
Сперва хочу вам в долг вменить
На курсы логики ходить.
Ваш ум, нетронутый доныне,
На них приучат к дисциплине,
Чтоб взял он направленья ось,
Не разбредаясь вкривь и вкось.
Гёте.
Логика
Мышление человека подчиняется логическим законам и протекает в логических формах независимо от науки логики. Многие люди мыслят логично, не зная ее правил. Разумеется, можно правильно мыслить, не изучив логику, однако нельзя и недооценивать практического значения этой науки.
Задача логики в том, чтобы научить человека сознательно применять законы и формы мышления и на основе этого логичнее мыслить, правильно сознавать окружающий мир. Знание логики повышает культуру мышления, вырабатывает навык мыслить “грамотно”, развивает критическое отношение к своим и чужим мыслям.
Логика – необходимый инструмент, освобождающий от личных, ненужных запоминаний, помогающий найти в массе информации то ценное, что нужно человеку. Она нужна “любому специалисту, будь он математик, медик, биолог”. (Анохин Н.К.)
Логика (греч. logike), наука о способах доказательств и опровержений; совокупность научных теорий, в каждой из которых рассматриваются определенные способы доказательств и опровержений. Различают индуктивную и дедуктивную логику, а в последней — классическую, интуиционистскую, конструктивную, модальную и др. Все эти теории объединяет стремление к каталогизации таких способов рассуждений, которые от истинных суждений-посылок приводят к истинным суждениям-следствиям; каталогизация осуществляется, как правило, в рамках логических. исчислений. Особую роль в ускорении научно-технического прогресса играют приложения логики в вычислительной математике, теории автоматов, лингвистике, информатике и др.
| Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания. Логика — это наука о формах и способах мышления. | |
| Появление математической или символической логики. Основы ее заложил немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646-1716). Он попытался построить первые логические исчисления, считал, что можно заменить простые рассуждения действиями со знаками и привел правила. Но Лейбниц высказал только идею, а развил ее окончательно англичанин Джордж Буль (1815-1864). Буль считается основоположником математической логики как самостоятельной дисциплины. В его работах логика обрела свой алфавит, свою орфографию и грамматику. Недаром начальный раздел математической логики называют алгеброй логики, или булевой алгеброй. |
Большой вклад в развитие математической логики внес русский математик П.С. Порецкий (1846-1907)
П.С. Эренфест (1880-1933) доказал, что операции алгебры логики можно иллюстрировать на физических и технических явлениях, а, следовательно, и применять.
Развитие математической логики особенно активизировалось в середине нашего века в связи с ее использованием в ВТ и программировании. Применение математической логики.
- Логика оказала влияние на развитие математики, прежде всего теории множеств, формальных систем, алгоритмов, рекурсивных функций.
- Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики).
- В гуманитарных науках (логика, криминалистика).
- Математическая логика является средством для изучения деятельности мозга - для решения этой самой важной проблемы биологии и науки вообще.
Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.
Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются понятие, высказывание и умозаключение.
Формы мышления
Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания. Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта. Понятие имеет две стороны: содержание и объем.
Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер — это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя».
Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров. Высказывание. Свое понимание окружающего мира человек формулирует в форме высказываний (суждений, утверждений). Высказывание строится на основе понятий и по форме является повествовательным предложением.
Высказывания могут быть выражены с помощью не только естественных языков, но и формальных. Например, высказывание на естественном языке имеет вид «Два умножить на два равно четырем», а на формальном, математическом языке оно записывается в виде: «2 * 2 = 4».Об объектах можно судить верно или неверно, то есть высказывание может быть истинным или ложным. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Примером истинного высказывания может служить следующее: «Процессор является устройством обработки информации».
Ложным высказывание будет в том случае, когда оно не соответствует реальной действительности, например: «Процессор является устройством печати». Высказывание не может быть выражено повелительным или вопросительным предложением, так как оценка их истинности или ложности невозможна. Конечно, иногда истинность того или иного высказывания является относительной. Истинность высказываний может зависеть от взглядов людей, от конкретных обстоятельств и так далее. Сегодня высказывание «На моем компьютере установлен самый современный процессор Репtium 4» истинно, но пройдет некоторое время, появится более мощный процессор, и данное высказывание станет ложным. Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо истинно, либо ложно. До сих пор мы рассматривали простые высказывания. На основании простых высказываний могут быть построены составные высказывания. Например, высказывание «Процессор является устройством обработки информации и принтер является устройством печати» является составным высказыванием, состоящим из двух простых, соединенных союзом «и».
Если истинность или ложность простых высказываний устанавливается в результате соглашения на основании здравого смысла, то истинность или ложность составных высказываний вычисляется с помощью использования алгебры высказываний.
Приведенное выше составное высказывание истинно, так как истинны входящие в него простые высказывания. Умозаключение. Умозаключения позволяют на основе известных фактов, выраженных в форме суждений (высказываний), получать заключение, то есть новое знание. Примером умозаключений могут быть геометрические доказательства.
Например, если мы имеем суждение «Все углы треугольника равны», то мы можем путем умозаключения доказать, что в этом случае справедливо суждение «Этот треугольник равносторонний ». Умозаключение - это форма мышления, с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (заключение). Посылками умозаключения по правилам формальной логики могут быть только истинные суждения. Тогда, если умозаключение проводится в соответствии с правилами формальной логики, то оно будет истинным. В противном случае можно прийти к ложному умозаключению.
Алгебра Высказываний
Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание.
В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые прописными буквами латинского алфавита. Рассмотрим два простых высказывания:
А = «Два умножить на два равно четырем».
В = «Два умножить на два равно пяти». Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 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».
Перейдем теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). В ней операцию логического умножения (конъюнкцию) принято обозначать значком "&" либо «^». Образуем составное высказывание Р, которое получится в результате конъюнкции двух простых высказываний:
Р = А & В. С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные Аи В, которые могут принимать значения «истина» (1) и «ложь» (0).
Сама функция логического умножения Р также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов (табл.).
| A | B | P=A&B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2 * 2 = 4 и 3 * 3 = 10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В= 0), по таблице определяем, что логическая функция принимает значение ложь (Р = 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".
Запишем теперь операцию логического сложения на формальном языке алгебры логики. Операцию логического сложения (дизъюнкцию) принято обозначать либо значком «V», либо знаком сложения «+». Образуем составное высказывание Р, которое получится в результате дизъюнкции двух простых высказываний:
Р = А ^ В.
С точки зрения алгебры высказываний мы записали формулу функции логического сложения, аргументами которой являются логические переменные А и В. Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов
| A | B | P=AvB |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического сложения. Рассмотрим, например, составное высказывание «2 * 2 = 4 или 3 * 3 = 10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение истина (Р = 1), то есть данное составное высказывание истинно. Логическое отрицание.Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным. Пусть А = «Два умножить на два равно четырем» — истинное высказывание, тогда высказывание Р = «Два умножить на два не равно четырем», образованное с помощью операции логического отрицания, — ложно. Операцию логического отрицания (инверсию) над логическим высказыванием А в алгебре логики принято обозначать А. Образуем высказывание Р, являющееся логическим отрицанием А:
Р = А. Истинность такого высказывания задается таблицей истинности функции логического отрицания.
| A | P= ¬A |
| 0 | 1 |
| 1 | 0 |
Истинность высказывания, образованного с помощью операции логического отрицания, можно легко определить с помощью таблицы истинности. Например, высказывание «Два умножить на два не равно четырем» ложно (А = 0), а полученное из него в результате логического отрицания высказывание «Два умножить на два равно четырем» истинно (Р = 1).
Логические выражения
ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ
Логические выражения. Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую входят логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции. Для записи составного высказывания в виде логического выражения на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними.
Запишем в форме логического выражения составное высказывание
«(2-2 = 5 или 2-2 = 4) и (2 -2*5 или 2-2*4)».
Проанализируем составное высказывание. Оно содержит два простых высказывания:
А = «2 * 2 = 5» — ложно (0),
В = «2 * 2 = 4» — истинно (1).Тогда составное высказывание можно записать в следующей форме:
«(А или В) и (А или В)».Теперь необходимо записать высказывание в форме логического выражения с учетом последовательности выполнения логических операций. При выполнении логических операций определен следующий порядок их выполнения: инверсия, конъюнкция, дизъюнкция. Для изменения указанного порядка могут использоваться скобки:
P = (A V B) & (¬A V ¬B) Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний, не обращаясь к смысловому содержанию высказываний.
Подставим в логическое выражение значения логических переменных и, используя таблицы истинности базовых логических операций, получим значение логической функции:
Р = (А V В) & (А V В) = (0 V 1)&(1 V 0) = 1 & 1 = 1.
Таблицы истинности. Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных).
При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий. Во-первых, необходимо определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Бели количество логических переменных равно n, то:
количество строк = 2n. В нашем случае логическая функция Р = ( имеет 2 переменные и, следовательно, количество строк в таблице истинности должно быть равно 4.
Во-вторых, необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций.
В нашем случае количество переменных равно двум, а количество логических операций — пяти, то есть количество столбцов таблицы истинности равно семи.
В-третьих, необходимо построить таблицу истинности с указанным количеством строк и столбцов, обозначить столбцы и внести в таблицу возможные наборы значений исходных логических переменных.
В-четвертых, необходимо заполнить таблицу истинности по столбцам, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности. Теперь мы можем определить значение логической функции для любого набора значений логических переменных.
| A | B | AvB | не А | не В | не А v не В | (AvB)&(не А v не В) |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак «=».
Докажем, что логические выражения А & В и А\/В равносильны. Построим сначала таблицу истинности логического выражения А & В.
| A | B | не В | не А | не А & не В |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
Теперь построим таблицу истинности логического выражения не(АvВ)
| А | В | АvB | не(AvB) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Значения в последних столбцах таблиц истинности совпадают, следовательно, логические выражения равносильны:
не А & не В = не(A v B)
Законы логики
Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений.
Закон тождества.
Всякое высказывание тождественно самому себе:
А = А
Закон непротиворечия.
Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:
А& ¬А = 0
Закон исключенного третьего.
Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:
A v ¬A = 1
Закон двойного отрицания.
Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:
¬¬A = A
Законы де Моргана.
¬(AvB) = ¬A & ¬B
¬(A&B) = ¬A v ¬BВажное значение для выполнения преобразований логических выражений имеют законы алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.
Закон коммутативности.
В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:
Логическое умножение: A&B = B&A
Логическое сложение: AvB = BvA
Закон ассоциативности.
Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
Логическое умножение: (A&B)&C = A&(B&C)
Логическое сложение: (AvB)vC = Av(BvC)
Закон дистрибутивности.
В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:Дистрибутивность умножения относительно сложения
аb + ас = а(b+с) — в алгебре
(А&В)v(А&С)=А&{ВvС)Дистрибутивность сложения относительно умножения
(А v В) & (А v С) = А v {В & C) Рассмотрим в качестве примера применения законов логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение:
(А & В) v (А & В).Воспользуемся законом дистрибутивности и вынесем за скобки A:
(А & В) V (A & В) = А & (В v В).По закону исключенного третьего В v ¬В =1, следовательно:
А& (ВvВ) « А&1 = А.
