Кафедра прикладной математики

ЛЕКЦИЯ № 4.

Тема: «элементы математической логики»

1. ЛОГИКА КАК НАУКА.

Познание истины – одна из важнейших потребностей человека. Каждый человек и человечество в целом стремятся к истине, добру и красоте. Все люди нуждаются в истинном знании, получении новой информации о мире, в котором они живут. Для чего? Для того чтобы жить, что в данном случае означает ориентироваться в быстро меняющейся обстановке, принимать правильные решения и на их основе совершать правильные действия.

Человек с древних времен стремился познать законы правильного мышления, т.е.логические законы. Наука логика помогает познанию этих законов. Законы развития есть у природы, общества, любой сложной системы и, конечно же, у самого мышления. Существуют даже мнение, что всякое движение нашей мысли, постигающей истину, добро и красоту, опирается на логические законы. Мы можем не осознавать их, но вынуждены всегда следовать этим законам, чтобы жить в обществе, общаться с людьми, понимать их и быть понятными.

В Древней Греции, Древней Индии, Древнем Риме законы и формы правильного мышления изучались в рамках ораторского искусства. Применение логических приемов рассужденияпозволяло ораторам более убедительно доносить до аудитории их точку зрения, склонять людей на свою сторону. Мыслить логично – значит мыслить точно и последовательно, не допускать противоречий в своих рассуждениях, уметь вскрывать логические ошибки.

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

Логика – одна из древнейших наук. Ее основателем считается величайший древнегреческий философ Аристотель, который первым систематизировал формы и правила мышления, обстоятельно исследовал категории «понятие» и «суждение», подробно разработал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления.

Предметом исследования науки логики является человеческое мышление. Мышление всегда осуществляется в каких-то формах. В логике выделяют следующие формы мышления: понятие, суждение, умозаключение. Примеры понятий: 1) апельсин; 2) трапеция; 3) белизна; 4) река Нил; 5) ураганный ветер; 6) студент строительной академии.

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

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

Например, признаками понятия апельсинявляются:круглый, оранжевый, упругий, сладкий, ароматный.Можно ли по этим признакам отличить апельсин от неапельсина? По ним легко отличить апельсин от яблока, но нельзя отличить апельсин от мандарина: большой мандарин можно спутать с маленьким апельсином. Поэтому для точной идентификации апельсина необходимо вести дополнительные признаки. Понятие имеет две основные логические характеристики: содержание и объем.

Содержание понятие – совокупность существенных признаков, отраженных в этом понятии.

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

Объем понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия.

Например, объем понятия река– это множество, состоящее из рек, носящих именаОбь, Иртыш, Енисей, Волга, Днепр, Днестр и др. Объем понятиястудентвключает в себя всех людей, которые когда-либо учились, учатся сейчас или будут учиться когда-нибудь.

Наглядная геометрическая иллюстрация объемов понятий и отношений между ними была предложена математиком, физиком и астрономом Леонардом Эйлером (1707 – 1781) и носит название кругов Эйлера.

Рассмотрим множество студентов некоторой группы (Е). Те студенты, которые занимаются спортом, образуют множество спортсменов (А). Те, кто увлекается литературой, образуют другое множество (В). Те, кто учится на отлично и на каникулах отдыхает в горах, образуют еще одно множество (С). Предположим, что среди студентов, составляющих множество С, нет ни одного, занимающегося спортом, т.е. множества С и А не имеют общих элементов. Множество студентов группы, которые знают пять иностранных языков (D), будет пустым, если таких полиглотов в группе нет. Данную ситуацию графически можно изобразить так:

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

Примеры суждений: 1) Этот апельсин вкусный; 2)Если прошел дождь, то на улице весна;3)На Луне живут лунатики, а на Марсе – марсиане.

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

Всякое суждение может быть либо истинным, либо ложным по своему содержанию.

Содержание суждения – это то, о чем в нем идет речь, его смысл.

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

Для того, чтобы вести рассуждения и оценивать их правильность, необходимо прежде договоритьсяпо каждому суждению, будем ли его рассматривать как истинное или ложное в данном конкретном случае. Например, суждениеОн – хороший шахматистможет быть как истинным, так и ложным, в зависимости от того, кто имеется в виду под местоимением «он». Следует отметить, что «договориться» можно только по отношению к простым суждениям. Значение же истинности сложных сужденийвычисляется. При вычислении истинности (ложности) сложного суждения содержание входящих в него простых суждений является незначимым. Интерес представляет то, чем суждения отличаются друг от друга, что характеризует каждое из них и неизменно для каждого из них, а именно их форма.

Логическая форма суждения – это его строение, способ связи его составных частей.

Форма суждения, в отличие от его содержания, объективна, т.е. не зависит от тех или иных взглядов того или иного человека. Следует определить логическую форму следующих суждений: 1) Все лошади едят овес; 2)Все реки впадают в море; 3)Все студенты – отличники; 4)Все книги имеют страницы; 5)Все планеты вращаются вокруг звезд. Во всех этих суждениях говорится о разном (у них различное содержание), но они имеют одинаковую логическую форму:Все S есть P. А сужденияВсе медузы не имеют головы; Люди не боги имеют другую логическую форму:Все S не есть P.

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

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

Все люди смертны.

Сократ – человек.

Сократ смертен.

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

Всякое умозаключение, так же как и суждение, имеет свою форму. Эта форма может быть логически правильной или логически неправильной. Так, в примере с Сократом форма умозаключения логически верная:

Все Sесть P.

Некоторые A есть S.

Некоторые A есть P.

Примеры верных умозаключений:

УМОЗАКЛЮЧЕНИЕ	ФОРМА УМОЗАКЛЮЧЕНИЯ
Четырехугольник (S1), у которого противоположные стороны параллельны (P), есть параллелограмм (S2). Квадрат (S3) – это четырехугольник (S1), у которого противоположные стороны параллельны (P). Квадрат – это параллелограмм.	Если S1 есть P, то S1 есть S2. Все S3 есть S1 и все S3 есть P. Все S3 есть S2.
Все граждане Украины имеют право на отдых. Я – гражданин Украины Я имею право на отдых	Все S есть P. A есть S. A есть P.
Если цветы поливают, то они не засохнут. Цветы засохли. Цветы не поливали.	Если S есть P1, То S не есть P2. S есть P2. S не есть P1.

О предметах можно судить верно или неверно, т.е. суждение может быть истиннымилиложным. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Примером истинного суждения может служить следующее: «Процессор является устройством обработки информации». Ложным суждение будет в том случае, когда оно не соответствует реальной действительности. Например: «Процессор является устройством печати». Суждение представляет собой относительно законченную мысль, отражающую объекты реального мира с их свойствами и отношениями. В большинстве суждений можно выделить понятие объекта и понятие о свойствах и отношениях этого объекта.

Понятие об объекте называется субъектоми обозначается латинской буквойS, а понятие о свойствах и отношениях объекта называетсяпредикатоми обозначается буквойР. Оба эти понятия – субъект и предикат называютсятерминамисуждения. Отношения между субъектом и предикатом выражается связками «есть», «не есть», «является», «состоит» и т.д. Именно связка придает суждению его логическую характеристику утверждения или отрицания.

Таким образом, каждое суждение состоит из трех элементов – субъекта, предиката и связки (двух терминов и связки). Состав суждения можно выразить общей формулой «SестьР» или «Sне естьР». Так, в суждении «Процессор является устройством обработки информации». «Процессор» – субъект, «устройством обработки информации» – предикат, «является» – связка. Суждение выражается в повествовательном предложении. Суждение не может быть выражено повелительным или вопросительным предложением, оценка истинности или ложности которых невозможна.

Правильно ли рассуждает человек, когда говорит:

УМОЗАКЛЮЧЕНИЕ	ИСТИННОСТЬ СУЖДЕНИЙ	ФОРМА УМОЗАКЛЮЧЕНИЯ
Если что-то есть металл, то оно проводит электрический ток. Алюминий проводит ток. Алюминий – металл.	Истина Истина Истина	Если S есть P1, то S есть P2. A есть P2. A есть P1.

Из истинных посылок получилось истинное заключение. Можно предположить, что, рассуждая по данной форме, получим из истинных посылок истинное заключение во всех случаях. Проверим это:

УМОЗАКЛЮЧЕНИЕ	ИСТИННОСТЬ СУЖДЕНИЙ	ФОРМА УМОЗАКЛЮЧЕНИЯ
Если что-то есть металл, то оно проводит электрический ток. Вода проводит ток. Вода – металл.	Истина Истина Ложь	Если S есть P1, то S есть P2. A есть P2. A есть P1.

Из истинных посылок получилось ложное заключение. Предположение о том, что, рассуждая по данной форме, всегда из истинных посылок получим истинное заключение, ошибочно. Следовательно, те, кто рассуждает по данной форме, либо ошибаются сами, либо вводят слушателей в заблуждение. Таким образом, услышав какую-нибудь фразу (рассуждение, умозаключение), можно, определив форму этого рассуждения и зная, правильна ли она логически, заранее сказать, будет ли истинным заключение.

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

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

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

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

С точки зрения содержания суждений в процессе мышления формируется истинное или ложное отражение мира, а если рассматривать мышлении со стороны формы, то имеет значение только его логическая правильность или неправильность.

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

Основной принцип формальной логики предполагает, что;

• каждое рассуждение, выраженное на некотором языке, имеет содержание и форму;

• содержание и форма различаются и могут быть разделены;

• содержание не оказывает влияния на правильность рассуждения (поэтому от него можно отвлечься);

• для оценки правильности рассуждения существенна лишь его форма;

• форму рассуждения необходимо выделить в «чистом» виде и затем на основе только формы решать вопрос о правильности рассуждения.

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

По отношению друг к другу понятия делятся на сравнимые и несравнимые.

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

Примеры несравнимых понятий: 1) Романс и кирпич; 2)безответственность и нитка. Остальные понятия называютсясравнимыми.

Сравнимые понятия делятся по объему на совместимые (объемы этих понятий совпадают полностью или частично) и несовместимые (объемы которых не совпадают ни по одному элементу).

Отношение между объемами понятий можно проиллюстрировать с помощью кругов Эйлера. Если имеются два каких-либо понятия XиY, то объем каждого из этих понятий можно представить в виде круга, а отношение между этими объемами – в виде пары кругов. Выделяют следующие виды отношений между сравнимыми понятиями: равнозначность (тождество), перекрещивание (пересечение), подчинение (субординация), соподчинение, противоположность и противоречие.

Обозначение сравнимых совместимых понятий:

ТОЖДЕСТВО	ПЕРЕСЕЧЕНИЕ	ПОДЧИНЕНИЕ
		(X подчинен Y)
X – Ю. Гагарин Y – первый космонавт	X – студент Y - спортсмен	X – лев Y - хищник

Если два понятия по своим объемам находятся в отношении подчинения, т.е. объем одного понятия входит в объем другого, тогда более широкое по объему понятие называется родовым, а подчиненное видовым.

Так, понятие «компьютер» родовое по отношению к видовому понятию «персональный компьютер», которое, в свою очередь, родовое по отношению к видовому понятию «IBM-совместимый компьютер».

Обозначения сравнимых несовместимых понятий:

СОПОДЧИНЕНИЕ	ПРОТИВОПОЛОЖНОСТЬ	ПРОТИВОРЕЧИЕ
(A и B соподчинены C)
A – береза, B – ель, C – дерево.	A – большой дом, B – маленький дом.	A – большой дом, B – небольшой дом.

Объем понятия – это множество (класс)предметов(элементов множества), каждый из которых характеризуется определенными признаками. Символическая записьозначает:a– элемент множестваM. Множество – одно из основных понятий современной математики, используемого почти во всех ее разделах. По словам одного из создателей теории множеств, немецкого математика Георга Кантора, - «Множество есть многое, мыслимое как единое».

2. ПОНЯТИЕ ОБ АЛГЕБРЕ ВЫСКАЗЫВАНИЙ.

Идею о возможности математизации логики высказал еще в XVIIв. немецкий логик Готфрид Вильгельм Лейбниц. Он пытался создать универсальный язык, с помощью которого каждому понятию и суждению можно было бы дать числовую характеристику и установить такие правила оперирования с этими числами, которые позволили бы сразу определить, истинно данное суждение (высказывание) или ложно. Т.е. он предполагал, что споры между людьми можно будет разрешать посредством вычислений. Но идея Лейбница оказалась неподтвержденной, так как до сих пор не найден способ свести человеческое мышление к некоторому математическому исчислению.

Подлинный прогресс науки, называемой математической логикой, был достигнут в серединеXIXв. прежде всего благодаря труду английского логика Джорджа Буля «Математический анализ логики». Он перенес на логику законы и правила алгебраических действий, ввел логические операции, предложил способ записи высказываний в символической форме. В трудах Дж. Буля и О. де Моргана математическая логика представлена как своеобразная алгебра – алгебра логики (алгебра высказываний).

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

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

Таким образом, объектами изучения алгебры высказываний являются высказывания.

Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно оно или ложно.

Если высказывание Aистинное, то будем писать «A= 1» и говорить «A– истинно». Если высказываниеAложное, то будем писать «A= 0» и говорить «Aложно».

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

3. ЛОГИЧЕСКИЕ ОПЕРАЦИИ

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

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

Обозначение инверсии:НЕА;;;NOTA.

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

А
1	0
0	1

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

Примечания:

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

2. Дважды или четырежды отрицающееся высказывание имеет то же самое значение истинности, что и исходное высказывание, трижды отрицающееся – что и отрицающееся один раз.

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

Обозначение конъюнкции: АИВ;;А&B;;AANDB.

Таблица истинности

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

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

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

Обозначение дизъюнкции:АИЛИВ;A ORB;А|B;;А+В.

Таблица истинности

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

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

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

Обозначения импликации:. Говорят: еслиА, тоВ;АвлечетВ;Вследует изА.

Таблица истинности

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

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

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

Обозначение эквивалентности:.

Таблица истинности

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

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

Рассмотренные свойства логических операций можно представить в следующем виде:

Инверсия истинна	Тогда и только тогда, когда	высказывание ложно
Дизъюнкция ложна Конъюнкция истинна		оба высказывания
Дизъюнкция истинна Конъюнкция ложна		хотя бы одно высказывание
Импликация ложна		из истинного высказывания следует ложное высказывание
Эквивалентность истинна		оба высказывания ложны или оба высказывания истинны

1. ЛОГИЧЕСКИЕ ПЕРЕМЕННЫЕ И ЛОГИЧЕСКИЕ ФУНКЦИИ

Буквы, обозначающие высказывания (А, В, …), можно рассматривать как именалогических переменных, так как ими можно заменить любые высказывания (с любым содержанием). Логические переменные принимают два значения : 0 и 1 («истина» и «ложь»). В алгебре логики из логических переменных,логических констант(0 и 1), знаков логических операций и скобок составляются логические выражения (подобно тому, как в алгебре чисел формируются арифметические выражения).

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

Выражения алгебры логики также называют формулами.

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

Высказывания бывают простые и сложные.

Простым называется высказывание, которое не содержит в себе других высказываний.

Примеры простых высказываний: 1) Идет дождь; 2)Студентам живется весело.

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

Скобки необходимы для определения порядка выполнения логических операций. Примеры сложных высказываний:

СЛОЖНОЕ ВЫСКАЗЫВАНИЕ	СОСТАВЛЯЮЩИЕ ПРОСТЫЕ ВЫСКАЗЫВАНИЯ	ФОРМА СЛОЖНОГО ВЫСКАЗЫВАНИЯ
Е = Идет дождь, а у меня нет зонта	А = Идет дождь; В = У меня есть зонт
Е = Когда живется весело, то и работа спорится	А = Живется весело; В = Работа спорится
Е = Идет налево – песнь заводит, направо – сказку говорит	А = Идет налево; В = Идет направо; С = Песнь заводит; D = Сказку говорит

В формальной логике принято, что всякое простое высказывание обязательно имеет одно из двух значений – истина или ложь. Следует отметить, что значение не всегда известно. Примерами таких высказываний являются недоказанные или неопровергнутые гипотезы: предположение о существовании жизни на Марсе и т.п. Однако в случае простого высказываниявсегда допустимодоговоритьсяо том, считать его истинным или ложным.

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

Реальную задачу получаем, как правило, в виде текста на естественном языке. И прежде чем приступить к ее решению, надо выделить простые высказывания, отношения (связи) между ними и перевести их на язык формул (формализовать условие задачи, определить форму сложного высказывания).

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

1. инверсия; 2) конъюнкция; 3) дизъюнкция; 4) импликация и эквивалентность.

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

ДАНА ФОРМУЛА:	ПОРЯДОК ВЫЧИСЛЕНИЙ:
	1)	- инверсия;
	2)	- конъюнкция;
	3)	- дизъюнкция;
	4)	- импликация;
	5)	- эквивалентность.
	1)	- инверсия;
	2)	- импликация в скобках;
	3)	- конъюнкция;
	4)	- дизъюнкция;
	5)	- эквивалентность.

Значение сложного высказывания определяется по таблице истинности. Рассмотрим примеры определения значений сложных высказываний.

Пример 1.

В аудитории оказалось разбито стекло. Преподаватель объясняет декану: Это сделал Коля или Саша. Но Саша этого не делал, так как в это время сдавал мне зачет. Следовательно, это сделал Коля. Прав ли преподаватель?

Формализуем данное сложное высказывание. Для этого сначала выделим составляющие простые высказывания и определим их количество (n):

К = Это сделал Коля.

С = Это сделал Саша.

n = 2.

Определим форму высказывания: .

Определим количество строк и столбцов в таблице истинности. Так как каждое из простых высказываний может принимать всего два значения (0 или 1), то количество разных комбинаций значений nвысказываний – 2ⁿ. Количество строк в таблице равно 2ⁿплюс 2 строки на заголовок. Количество столбцов в таблице равно сумме количества простых высказываний (n) и количества разных логических операций, входящих в сложное высказывание. В данном случае:

• количество строк – 2²+ 2 = 6;

• количество столбцов – 2 + 4 = 6.

Начертим таблицу и заполним ее в соответствии с определениями логических операций последовательно по столбцам. Сначала заполняем 1-й и 2-й столбцы, затем вычисляем значения 3-го столбца по значениям 2-го, потом значения 4-го – по значениям 1-го и 2-го и т.д.:

1	2	3	4	5	6
К	С
0	0	1	0	0	1
0	1	0	1	0	1
1	0	1	1	1	1
1	1	0	1	0	1

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

Пример 2.

Построим таблицу истинности для высказывания

.

Алгоритм построения таблицы истинности сложного высказывания (на примере n=3):

1. Вычислить количество строк и столбцов таблицы истинности.

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

В высказывание Евходят 3 переменные:А, В, С (n=3) и 4 логические операции: инверсияВ, инверсияС, дизъюнкция, импликация. Имеем 2³+ 2 = 10 строк и 3 + 4 = 7 столбцов.