 |
Аксиомы алгебры высказываний
|
|
|
|
Одним из возможных вариантов аксиоматизации алгебры высказываний является следующая система аксиом:
A1: p → (q → p)
A2: ((p → (q → r)) → ((p → q) → (p → r))
A3: p ˄ q → p
A4: p ˄ q → q
A5: p → (q → (p ˄ q))
A6: p → (p ˅ q)
A7: q → (p ˅ q)
A8: (p → r) → ((q → r) → ((p ˅ q) → r))
A9: ͞p → (p → q)
A10: (p → q) → ((p → ͞q) → ͞p)
A11: p ˅ ͞p
вместе с единственным правилом: если p и p→q - выводимые формулы, то q также выводима (Modus ponens).
Правило модус поненс обычно называется правилом отделения или условным силлогизмом и позволяет от утверждения гипотетического суждения p→q и утверждения его основания p (антецедента) перейти к утверждению следствия q (консеквента).
Интерпретация импликации как гипотетического суждения позволяет связать приведённую выше систему аксиом с учением о силлогизме. Первая аксиома в этом случае оказывается записью закона достаточного основания. Дествие законов противоречия и исключенного третьего обеспечивается таблицей истинности унарной связки отрицания. Отсюда ясно, что переменные алгебры высказываний представляют собой, во-первых, не любые высказывания, но именно логические суждения.
Вторая аксиома формализует аксиому силлогизма. Это означает, что для пропозициональных переменных действуют те же правила, что для суждений о принадлежности предмета классу предметов. Сам по себе этот факт не имеет отношения к основной задаче алгебры высказываний в силу исключения из сферы её интересов содержания составляющих суждения понятий, однако он важен для понимания механизма формально-логических операций. Содержалие импликацию формулы по сути выражают правильные силлогизмы со специфической структурой, которая сверх того, что она обеспечивает истинный вывод из истинных посылок, ещё и позволяет установить чёткую зависимость истинности или ложности вывода от истинности или ложности посылок.
|
|
|
Теорема корректности исчисления суждений утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Все остальные тавтологии можно получить из аксиом с помощью правила вывода – это так называемая теорема полноты алгебры высказываний. Булева алгебра является обобщением алгебры высказываний и позволяет рассматривать, например, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др. Принцип двумерной логики в приведённой выше системе аксиом закрепляется одиннадцатой аксиомой, выражающей закон исключенного третьего.
Специальные задачи информатики и машинного программирования требуют сведения логических связок к наиболее элементарным операциям с бинарными переменными. Это достигается представлением импликации формулой вида: ͞p ˅ q, сводящей импликацию к связкам дизъюнкции и инверсии. Тавтология (p → q) ↔ ͞p ˅ q устанавливается на основании совпадения таблиц истинности данных формул. Связки дизъюнкции, коньюнкции и отрицания называются в информатике логическими операторами ИЛИ И и НЕ, или логическим сложением, умножением и отрицанием соответственно. Поскольку любые операции с бинарными переменными сводимы к данным трём операторам, говорят, что они образуют функционально полную систему.
Контрольные вопросы к лекции 7:
1) Назовите виды условных силлогизмов. В чём их особенности?
2) Опишите модусы условно-категорического силлогизма и их особенности.
|
|
|
3) Какой силлогизм называется разделительным? Опишите его виды и правила.
4) Дайте определения основных понятий алгебры высказываний: пропозициональной переменной, пропозициональной формулы, пропозициональной связки и истинностного значения.
5) Какова основная задача алгебры высказываний? В чём её отличие от задачи силлогизма?
6) Что такое тавтология в алгебре высказываний?
7) Опишите связь алгебры высказываний с учением о силлогизме.
ЗАДАЧИ
1. В следующих условно-категорических силлогизмах определите их вид, модус, исследуйте, будет ли силлогизм правильным, и если он ошибочен, то укажите, в чем состоит допущенная логическая ошибка:
1) «Если в лесу вырастет густой ельник, то насекомых в этом лесу станет меньше; если насекомых в лесу станет меньше, то уменьшится число живущих в этом лесу певчих птиц; следовательно, если в лесу вырастет густой ельник, то певчих птиц в этом лесу станет меньше», 2) «Если больной выздоравливает, то температура у него понижается; температура у больного не понизилась; следовательно, больной не выздоравливает»; 3) «Чтобы тень от земли, надвигающаяся на поверхность луны во время лунных затмений, была круглой, необходимо, чтобы земля имела форму шара; тень от земли, надвигающаяся на поверхность луны во время лунных затмений, круглая; следовательно, земля имеет форму шара»; 4) «Если имеются признаки, что у страдающего малярией приближается припадок, то ему надо принять хинин; имеются признаки, что у страдающего малярией приближается припадок; следовательно, ему надо принять хинин»; 5) «Если враг не сдаётся, будет отдан приказ об его уничтожении; враг не сдается; следовательно, будет отдан приказ об его уничтожении»; 6) «Если бы земля не была когда-то покрыта морем, то в ней не могли бы встречаться пласты, состоящие из раковин морских животных; но в земле повсеместно встречаются пласты, состоящие из раковин морских животных, следовательно, земля была когда-то покрыта морем»; 7) «Если яблоки на яблоне созрели, то они должны осыпаться; яблоки на яблоне осыпались; следовательно, они созрели».
2. В следующих разделительных силлогизмах определите их вид, модус, исследуйте, будет ли силлогизм правильным, и если он ошибочен, то укажите, в чём состоит допущенная логическая ошибка:
|
|
|
1) «Каждый телескоп есть или рефрактор, или рефлектор; каждый рефлектор есть или металлический, или зеркальный; следовательно, каждый телескоп есть или рефрактор, или металлический рефлектор, или зеркальный рефлектор»; 2) «Каждое растение принадлежит или к высшим, или к низшим; если растение принадлежит к низшим, оно всасывает вещества своей поверхностью; следовательно, каждое растение есть или высшее, или всасывающее вещества своей поверхностью»; 3) «Бактерии имеют форму или шарообразную (кокки), или цилиндрическую (палочки), или извитую (вибрионы); бактерии туберкулёза» не принадлежат ни к коккам, ни к вибрионам; следовательно, бактерии туберкулёза принадлежат к палочкам»; 4) «Если папоротники – разноспоровые, то заростки у них – двуполые, а если папоротники – равноспоровые, то заростки у них раздельнополые; но папоротники бывают только или равноспоровые, или разноспоровые; поэтому заростки у папоротников могут быть только двуполые или раздельнополые»; 5) «Позвоночные животные бывают или млекопитающие, или птицы, или рыбы, или земноводные; ящерица, будучи позвоночным животным, не есть ни млекопитающее, ни птица, ни рыба; следовательно, ящерица– земноводное»; 6) «Млекопитающие бывают или сумчатые, или одноутробные; кенгуру–сумчатое млекопитающее; следовательно, кенгуру не принадлежит к одноутробным»; 7) «Победа на состязании в беге обусловливается или природными данными, или тренировкой; победа Сергеева на состязании в беге обусловлена тренировкой; следовательно, победа Сергеева на состязании в беге не обусловлена природными данными»; 8) «Победа на состязании в беге обусловливается или природными данными, или тренировкой; победа Сергеева на состязании в беге обусловлена не природными данными; следовательно, победа Сергеева на состязании в беге обусловлена тренировкой».
Пример решения логической задачи средствами алгебры высказываний:
Некий любитель приключений отправился в кругосветное путешествие на яхте, оснащённой бортовым компьютером. Его предупредили, что чаще всего выходят из строя три узла компьютера — a, b, c, и дали необходимые детали для замены. Выяснить, какой именно узел надо заменить, он может по сигнальным лампочкам на контрольной панели. Лампочек тоже ровно три: x, y и z. Инструкция по выявлению неисправных узлов такова:
|
|
|
1. если неисправен хотя бы один из узлов компьютера, то горит по крайней мере одна из лампочек x, y, z;
2. если неисправен узел a, но исправен узел с, то загорается лампочка y;
3. если неисправен узел с, но исправен узел b, загорается лампочка y, но не загорается лампочка x;
4. если неисправен узел b, но исправен узел c, то загораются лампочки x и y или не загорается лампочка x;
5. если горит лампочка х и при этом либо неисправен узел а, либо все три узла a, b, c исправны, то горит и лампочка y.
В пути компьютер сломался. На контрольной панели загорелась лампочка x. Тщательно изучив инструкцию, путешественник починил компьютер. Но с этого момента и до конца плавания его не оставляла тревога. Он понял, что инструкция несовершенна, и есть случаи, когда она ему не поможет.
Какие узлы заменил путешественник? Какие изъяны он обнаружил в инструкции?
Решение.
Введем обозначения для логических высказываний:
a — неисправен узел а; x — горит лампочка х;
b — неисправен узел b; y — горит лампочка y;
с — неисправен узел с; z — горит лампочка z.
Правила 1–5 выражаются следующими формулами:
1) a˅b˅c→x˅y˅z
2) a˄c̅ →y
3) c˄b̅ →y˅x̅
4) b˄c̅ →(x˄y˅x̅)
5) (a˅a̅˄b̅˄c̅)˄x→y
Формулы 1–5 истинны по условию, следовательно, их конъюнкция тоже истинна:
(a˅b˅c→x˅y˅z)˄(a˄c̅ →y)˄(c˄b̅ →y˅x̅)˄(b˄c̅ →(x˄y˅x̅))˄((a˅a̅˄b̅˄c̅)˄x→y)=1
Выражая импликацию через дизъюнкцию и отрицание, получаем:
(a̅˄b̅˄c̅˅x˅y˅z)˄(a̅˅c˅y)˄(c̅˅b˅y˄x̅)˄(b̅˅c˅x˄y˅x̅)˄(͞ ((a˅a̅)˄(a˅b̅)˄(a˅c̅)˄x)˅y) = (a̅˄b̅˄c̅˅x˅y˅z)˄(a̅˅c˅y)˄(c̅˅b˅y˄x̅)˄(b̅˅c˅x˄y˅x̅)˄(a̅˄b˅a̅˄c˅x̅˅y) = 1
Подставляя в это тождество конкретные значения истинности x =1, y =0, z =0, получаем:
(a̅˅c)˄(c̅˅b)˄(b̅˅c)˄(a̅˄b˅a̅˄c)=(a̅˄c̅˅a̅˄b˅c˄b)˄(b̅˄a̅˄c˅c˄a̅˄b˅a̅˄c)=a̅˄b˄c=1
Отсюда следует, что a=0, b=1, c=1.
Ответ на первый вопрос задачи: нужно заменить блоки b и c; блок а не требует замены.
Ответ на второй вопрос задачи получите самостоятельно.
Задачи для решения средствами алгебры высказываний:
|
|
|
1) Определить, кто из учеников участвовал в олимпиаде, если известно, что:
если Иванов не участвовал или Петров участвовал; то Сидоров участвовал, если Иванов не участвовал, то Сидоров не участвовал.
2) В нарушении правил обмена валюты (ПОВ) были замечены 4 рабочих банка А, В, С, D. Кто из подозреваемых нарушил ПОВ, если известно, что:
если банк А нарушил, то и В нарушил; если В нарушил, то С нарушил или А не нарушил; если D не нарушил, то А нарушил; если D нарушил, то и А нарушил.
3) Какие из учебных предметов: информатика, химия, математика, русский – должны быть внесены в расписание при следующих условиях: если вносить информатику, то вносить химию; если не вносить русский, то не вносить и химию; неверно, что если внести математику, то внести и русский.
4) Аня, Вика и Сергей решили пойти в кино. Максим высказал предположение: Аня пойдет в кино, если пойдут Вика и Сережа; Аня и Сережа в кино пойдут вместе или оба останутся дома; чтобы Сережа пошел в кино, необходимо, чтобы пошла Вика. Когда ребята пошли в кино, оказалось, что из 3-х утверждений Максима только 2 истины. Кто из ребят пошел в кино?
5) Миша решил поступать в институт и послал домой 3 SMS: если я сдам математику, то изложение напишу только при условии, что не завалю химию; не может быть, что я завалил и изложение, и математику; достаточное условие для завала по химии – это “2” по изложению. После сдачи оказалось, что одно из Мишиных сообщений было ложным. Каковы результаты вступительных экзаменов у Миши?
6) Кто из учеников идет на олимпиаду по физике, если известно следующее: если Миша идет, то идет Аня, но не идет Саша; если Саша не идет на олимпиаду, то идет Аня, но не идет Миша; если Аня идет, то идет Миша, но не идет Саша.
7) Три фирмы, специализирующиеся на производстве и продаже компьютеров, стремились получить максимальную прибыль за год. Один экономист высказал предположение: фирма А получит максимальную прибыль, если ее получит фирма В и С; либо фирма А и С одновременно получают, либо одновременно не получают; для того, чтобы С получила прибыль, необходимо, чтобы и фирма В получила прибыль. По завершению года оказалось, что лишь два утверждения верно. Какие фирмы получили прибыль?
8) Маша, Жанна, Таня и Оля пришли на День рождения к своей подруге. Подарки они положили в одно место. Это были: цветы, кукла, раскраска и лото. Именинница знала следующее: Маша, Жанна, девочка, которая подарила куклу, и девочка, которая подарила раскраску - учатся в одном классе; Оля, девочка, которая подарила лото, девочка, которая подарила раскраску, и девочка, которая подарила цветы - живут на одной улице; Маша не дарила цветы. Определите, кто из девочек подарил какой подарок.
9) Восемь школьников, оставшиеся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал были получены следующие ответы:
Соня: «Это сделал Володя».
Миша: «Это ложь!»
Володя: «Я разбил!»
Аня: «Это я разбила!»
Оля: «Аня не разбивала!»
Рома: «Разбила либо Соня, либо Оля…»
Коля: «Девочки этого не делали».
Толя: «Коля разбил!»
Кто разбил окно, если известно, что из этих восьми высказываний истинно только 2?
10) Четыре девушки подали заявки на конкурс красоты. Их имена: Таня, Женя, Полина и Вика. Одна из девушек блондинка, другая – шатенка, третья – брюнетка, четвертая – рыжеволосая. До начала конкурса были выдвинуты следующие предположения:Таня – блондинка, а Полина – брюнетка; блондинка - Женя, а Вика – рыжеволосая; Таня - шатенка, а Женя – брюнетка. Как оказалось впоследствии, в каждом утверждении только одно предположение оказалось верным. Определите цвет волос каждой девушки.
11) Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.
Кто сделал это? – спросила мама.
Коля не бил по мячу, - сказал Саша. – Это сделал Ваня.
Разбил Коля, Саша не играл в футбол дома – ответил Ваня.
Так я и знала, что вы друг на друга сваливать будете, - рассердилась мама. – Ну, а ты что скажешь? – спросила она Колю.
Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, - сказал Коля.
Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорил правду. Кто разбил вазу?
12) Восемь школьников, оставшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:
Егор: «Разбил Андрей!»
Света: «Вика разбила».
Оля: «Разбила Света».
Миша: «Это кто-то с улицы!»
Надя: «Да, Оля права…»
Коля: «Это либо Вика, либо Света!»
Андрей: «Ни Вика, ни Света этого не делали».
Вика: «Андрей не бил!»
Кто разбил окно, если известно, что из этих восьми высказываний истинно ровно три?
Лекция 8
Индуктивные умозаключения - это умозаключения, в которых из частных посылок делают общий вывод. Исчерпывающее индуктивное обобщение, когда рассматриваемый класс конечен и не слишком велик, так что мы можем исследовать все частные случаи, называется полной индукцией. Полная индукция – это умозаключение, в котором на основе принадлежности признака каждому элементу класса делается вывод о его принадлежности классу в целом.
Обычно число обобщаемых случаев бесконечно велико и индукция является неполной. Неполная индукция – это умозаключение, в котором на основе принадлежности признака лишь некоторым элементам класса делают вывод о его принадлежности классу в целом.
Схема полной индукции:
S1 имеет признак P
S2 имеет признак P
S3 имеет признак P
……………
S50 имеет признак Р
S1, S2, S3,…, S50 - образуют весь класс S
Все S имеют признак Р
Здесь вывод достоверен.
Полная индукция часто рассматривается как разновидность дедуктивного вывода.
Схема неполной индукции:
S1 имеет признак P
S2 имеет признак P
S3 имеет признак P
……………
Sn имеет признак Р
S1, S2, S3,…, Sn - образуют лишь часть объема S
(Вероятно) все S есть Р
Неполная индукция может быть популярной и научной
Популярная индукция – это умозаключение, в котором путем перечисления фактов по случайному признаку заключают о принадлежности этого признака всему классу явлений. Это приводит к ненадежности выводов, причем неконтролируемой ненадежности, поскольку невозможно оценить меру достоверности (вероятность истинности) вывода.
Научная индукция – это умозаключение, в котором обобщение строится путем отбора существенных признаков. Для научной индукции характерна систематичность и методичность отбора данных для обобщения выраженных в наборе суждений, обосновывающих вывод, стремление использовать в конкретных обобщениях знание сущностных свойств и закономерностей предметной области, законов статистики. Так, к научной индукции можно отнести многообразные статистические методы, широко используемые в науке и практике.
Неполная индукция Бэкона
В исследованиях причинной связи, т. е. связи причины и действия, большую роль играют умозаключения, или выводы, известные под названием индукции Бэкона. Выводы эти были впервые указаны в логике английским философом-материалистом Френсисом Бэконом (1561–1626). Правила индукции Бэкона были подробно изложены и переработаны с учётом фактов и методов естественных наук, сложившихся в конце XVIII и в первой трети XIX века, английскими учёными Джоном Гершелем и Джоном Стюартом Миллем.
Основных видов или методов бэконовской (или миллевской) индукции пять: 1) метод сходства (или, как его ещё называют, метод единственного сходства); 2) метод различия (или метод единственного различия); 3) соединённый метод сходства и различия; 4) метод остатков и 5) метод сопутствующих изменений.
Метод сходства
Метод сходства есть вывод о причине явления, получающийся из сравнения ряда случаев, подобранных таким образом, чтобы явление, причину которого мы ищем, наступало во всех этих случаях и чтобы случаи эти, различные во всём, оказались бы сходными между собой в одном общем для всех них обстоятельстве.
В общей форме умозаключение по методу единственного сходства может быть представлено следующей таблицей:
| Случаи | Наблюдаемые обстоятельства | Действие, причина которого должна быть установлена |
| ABC | ɑ | |
| ADE | ɑ | |
| AFG | ɑ |
Вывод: причина явления ɑ есть обстоятельство А.
Из схемы видно, что во всех трёх случаях имеет место некоторое действие а, причина которого и составляет предмет исследования. Если бы причиной наступления ɑ было, например, обстоятельство В, входившее в состав первого случая, то во втором случав ɑ не могло бы наступить, так как обстоятельства B во втором случае не оказалось. По тем же основаниям должны быть исключены обстоятельства С, D, Е, F и G. Все они, появляясь в одном из рассмотренных случаев, отсутствовали во всех остальных и поэтому не могли быть причиной ɑ, которое наступило во всех случаях. По исключении В, С, D, Е, F и G остаётся одно только обстоятельство А. Так как оно единственное, имевшее место во всех случаях, и так как все остальные обстоятельства отпали в качестве возможных причин явления, то остаётся заключить, что именно обстоятельство А есть причина наступления явления ɑ.
В нашем примере опыты поставлены так, что сходным оказывается одно единственное обстоятельство. На этом основании метод сходства иногда называют методом единственного сходства.
Метод различия
Метод различия есть вывод о причине явления, получающийся из сравнения случая, когда явление наступает, со случаем, когда оно не наступает. При этом оба случая совершенно сходны между собой во всех обстоятельствах, кроме одного. Обстоятельство это присутствует в первом случае, когда явление наступает, и отсутствует во втором, когда явления нет. Ход умозаключения по методу различия изображается следующей таблицей:
| Случаи | Наблюдаемые обстоятельства | Действие, причина которого должна быть установлена |
| ABCDE | ɑ | |
| BCDE | - |
Вывод: причина явления ɑ есть обстоятельство А.
Ни одно из обстоятельств В, С, D, Е не могло быть причиной явления ɑ, так как это обстоятельство имелось налицо не только в первом, но и во втором случае. Остаётся одно единственное обстоятельство А, так как опыт показывает, что при наличии А появляется и ɑ и, наоборот, при отсутствии А не возникает и ɑ. Отсюда заключаем, что обстоятельство А есть причина явления а.
|
|
|
