Виды высказываний
Логические высказывания принято подразделять на два вида: элементарные логические высказывания и составные логические высказывания.
Составное логическое высказывание - это высказывание, образованное из других высказываний с помощью логических связок.
Логическая связка - это любая логическая операция над высказыванием. Например, употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если… , то», «тогда и только тогда» являются логическими связками.
Элементарные логические высказывания - это высказывания не относящиеся к составным.
Примеры: «Петров - врач», «Петров - шахматист» - элементарные логические высказывания. «Петров - врач и шахматист» - составное логическое высказывание, состоящие из двух элементарных высказываний, связанных между собой при помощи связки «и».
Связь с математической логикой
Обычная логика двухзначна, то есть приписывает высказываниям только два возможных значения: истинно оно или ложно .
Пусть - высказывание. Если оно истинно, то пишут , если ложно, то .
Основные операции над логическими высказываниями
Отрицание логического высказывания - логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот.
Конъюнкция двух логических высказываний - логическое высказывание, истинное только тогда, когда они одновременно истинны.
Дизъюнкция двух логических высказываний - логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.
Импликация двух логических высказываний A и B - логическое высказывание, ложное только тогда, когда B ложно, а A истинно.
Равносильность (эквивалентность) двух логических высказываний - логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.
Кванторное всеобщности () - логическое высказывание, истинное только тогда, когда для каждого объекта x из заданной совокупности высказывание A(x) истинно.
Кванторное логическое высказывание с квантором существования () - логическое высказывание, истинное только тогда, когда в заданной совокупности существует объект x, такой, что высказывание A(x) истинно.
См. также
- Утверждение
Примечания
Литература
- Карпенко, А. С. Современные исследования в философской логике // Логические исследования. Вып. 10. - М.: Наука, 2003. ISBN 5-02-006257-X - С. 61-93.
- Крипке, С. А. Витгенштейн о правилах и индивидуальном языке / Пер. В. А. Ладова, В. А. Суровцева. Под общ. ред. В. А. Суровцева. - Томск: Изд-во Том. ун-та, 2005. - 152 с. - (Библиотека аналитической философии). ISBN 5-7511-1906-1
- Курбатов, В. И. Логика. Систематический курс. - Ростов н/Д: Феникс, 2001. - 512 c. ISBN 5-222-01850-4
- Шуман, А. Н. Современная логика: теория и практика. - Минск: Экономпресс, 2004. - 416 с. ISBN 985-6479-35-5
- Макарова, Н. В. Информатика и ИКТ. - Санкт-Петербург: Питер Пресс, 2007 ISBN 978-5-91180-198-4 - С. 343-345.
- Кондаков Н. И. Логический словарь / Горский Д. П.. - М .: Наука, 1971. - 656 с.
Wikimedia Foundation . 2010 .
Смотреть что такое "Высказывание (логика)" в других словарях:
Высказывание: Высказывание (логика) предложение, которое может быть истинно или ложно. Высказывание (лингвистика) предложение в конкретной речевой ситуации. См. также Суждение … Википедия
- (от греч. logos слово, понятие, рассуждение, разум), или Формальная логика, наука о законах и операциях правильного мышления. Согласно основному принципу Л., правильность рассуждения (вывода) определяется только его логической формой, или… … Философская энциклопедия
Раздел логики, в котором изучаются истинностные взаимосвязи между высказываниями. В рамках данного раздела высказывания (пропозиции, предложения) рассматриваются только с т.зр. их истинности или ложности, безотносительно к их внутренней субъектно … Философская энциклопедия
логика высказываний - ЛОГИКА ВЫСКАЗЫВАНИЙ, пропозициональная логика раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, простые высказывания при этом выступают как… … Энциклопедия эпистемологии и философии науки
Грамматически правильное повествовательное предложение, взятое вместе с выражаемым им смыслом. В логике употребляется несколько понятий В., существенно различающихся между собой. Прежде всего это понятие дескриптивного, или о п и с а тельного,… … Философская энциклопедия
Логика Бэрроуза Абади Нидхэма (англ. Burrows Abadi Needham logic) или BAN логика (англ. BAN logic) это формальная логическая модель для анализа знания и доверия, широко используемая при анализе протоколов… … Википедия
Центральный раздел логики, в котором изучается субъектно предикатная структура высказывании и истинностные взаимосвязи между ними. Л.п. представляет собой содержательное расширение логики высказываний. В рамках данного раздела любое высказывание… … Философская энциклопедия
Или Логика науки, применение идей, методов и аппарата логики в анализе научного познания. Развитие логики всегда было тесно связано с практикой теоретического мышления и прежде всего с развитием науки. Конкретные рассуждения дают логике материал … Философская энциклопедия
Логика, созданная как наука Аристотелем (384-322 г. до н.э.), на протяжении столетий использовалась для развития многих областей знания, включая теологию, философию, математику.
Она - тот фундамент, на котором построено все здание математики. По сути, логика — это наука о рассуждениях, которая позволяет определить истинность или ложность того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Логика применяется также в информатике для построения компьютерных программ и доказательства их корректности. Понятия, методы и средства логики лежат в основе современных информационных технологий. Одна из основных целей этой работы — изложить основы математической логики, показать, как она используется в информатике, и разработать методы анализа и доказательства математических утверждений.
Логические представления - описание исследуемой сис-темы, процесса, явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления и их составляющие характеризуются опре-деленными свойствами и набором допустимых преобразо-ваний над ними (операций, правил вывода и т.п.), реализую-щих разработанные в формальной (математической) логике правильные методы рассуждений — законы логики .
Понятие высказывания
Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Иными словами, утверждение об истинности или ложности высказывания должно иметь смысл. Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности , или истинностным значением.
Например, высказывания Дважды два четыре и Город Челябинск находится в азиатской части России истинные, а высказывания Три больше пяти и Река Дон в настоящее время впадает в Каспийское море ложны, так как не соответствуют действительности. Истинные высказывания принято обозначать T (true ) или И (истина ), а ложные, соответственно, F (false ) или Л (ложь ). В информатике истинность принято обозначать 1 (двоичная единица), а ложность - 0 (двоичный ноль).
Вот примеры предложений, не являющихся высказываниями:
Кто вы? (вопрос),
Прочтите эту главу до следующего занятия (приказ или восклицание),
Это утверждение ложно (внутренне противоречивое утверждение),
Площадь отрезка меньше длины куба (нельзя сказать истинно это предложение или ложно, т.к. не имеет смысла).
Мы будем обозначать высказывания буквами латинского алфавита р , q , r , Например, р может обозначать утверждение Завтра будет дождь , а q — утверждение Квадрат целого числа есть число положительное .
Логические связки
В обыденной речи для образования сложного предложения из простых используются связки — особые части речи, соединяющие отдельные предложения. Наиболее часто употребляются связки и , или , не , если ... то , только если , и тогда и только тогда . В отличие от обыденной речи, в логике смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей. Высказывание, не содержащее связок, называется простым . Высказывание, содержащее связки, называется сложным . Логические связки также называют логическими операциями над высказываниями.
Пусть р и q обозначают высказывания
р: Джейн водит автомобиль,
q: У Боба русые волосы.
Сложное высказывание
Джейн водит автомобиль и у Боба русые волосы состоит из двух частей, объединенных связкой и . Это высказывание может быть символически записано в виде
где символ обозначает слово и на языке символических выражений. Выражение называется конъюнкцией высказываний р и q .
Встречаются также следующие варианты записи конъюнкции:
Точно так же высказывание
Джейн водит автомобиль или у Боба русые волосы.
символически выражается как
где обозначает слово или в переводе на символический язык. Выражение называется дизъюнкцией высказываний р и q .
Опровержение, или отрицание высказывания p обозначается через
Таким образом, если р есть высказывание Джейн водит автомобиль , то - это утверждение Джейн не водит автомобиль .
Если r есть высказывание Джо нравится информатика , то Джейн не водит автомобиль и у Боба русые волосы или Джо любит информатику символически запишется как
.
И наоборот, выражение
это символическая форма записи высказывания Джейн водит автомобиль, у Боба волосы не русые и Джо нравится информатика .
Рассмотрим выражение . Если некто говорит: "Джейн водит автомобиль и у Боба русые волосы" , то мы, естественно, представляем себе Джейн за рулем автомобиля и русоволосого Боба. В любой другой ситуации (например, если Боб не русоволос или Джейн не водит автомобиль) мы скажем, что говорящий не прав.
Возможны четыре случая, которые нам необходимо рассмотреть. Высказывание р может быть истинным (Т ) или ложным (F ) и независимо от того, какое истинностное значение принимает р , высказывание q может также быть истинным (Т ) или ложным (F ). Таблица истинности перечисляет все возможные комбинации истинности и ложности сложных высказываний.
Итак, конъюнкция истинна тогда и только тогда, когда истинны оба высказывания p и q , то есть в случае 1.
Точно так же рассмотрим высказывание Джейн водит автомобиль или у Боба русые волосы , которое символически выражается как . Если некто скажет: "Джейн водит автомобиль или у Боба русые волосы", то он будет не прав только тогда, когда Джейн не сможет управлять автомобилем, а Боб не будет русоволосым. Для того чтобы все высказывание было истинным, достаточно, чтобы одна из двух составляющих его компонент была истинной. Поэтому имеет таблицу истинности
Дизъюнкция ложна только в случае 4, когда оба р и q ложны.
Таблица истинности для отрицания имеет вид
Истинностное значение всегда противоположно истинностному значению р. В таблицах истинности отрицание всегда оценивается первым, если только за знаком отрицания не следует высказывание, заключенное в скобки. Поэтому интерпретируется как , так что отрицание применяется только к р . Если мы хотим отрицать все высказывание, то это записывается как .
Символы и называют бинарными связками, так как они связывают два высказывания. Символ ~ является унарной связкой, так как применяется только к одному высказыванию.
Еще одна бинарная связка - это исключающее или, которое обозначается через . Высказывание истинно, когда истинно p или q , но не оба одновременно. Эта связка имеет таблицу истинности
Используя слово или , мы можем иметь в виду исключающее или . Например, когда мы говорим, что р — либо истина, либо ложь, то, естественно, предполагаем, что это не выполняется одновременно. В логике исключающее или используется довольно редко, и в дальнейшем мы, как правило, будем обходиться без него.
Рассмотрим высказывание
,
где скобки использованы, чтобы показать, какие именно высказывания являются компонентами каждой связки.
Таблица истинности дает возможность однозначно указать те ситуации, когда высказывание является истинным; при этом мы должны быть уверены, что учтены все случаи. Поскольку сложное высказывание содержит три основных высказывания р
, q
и r
, то возможны восемь случаев
| Случай | p | q | r | |
||
| T | T | T | F | F | T | |
| T | T | F | F | F | T | |
| T | F | T | T | T | T | |
| T | F | F | T | F | T | |
| F | T | T | F | F | F | |
| F | T | F | F | F | F | |
| F | F | T | T | T | T | |
| F | F | F | T | F | F |
При нахождении значений истинности для столбца мы используем столбцы для и r , а также таблицу истинности для . Таблица истинности для показывает, что высказывание истинно лишь в том случае, когда истинны оба высказывания и r . Это имеет место лишь в случаях 3 и 7.
Заметим, что при определении значений истинности для столбца 
играет роль только истинность высказываний p
и . Таблица истинности для показывает, что единственный случай, когда высказывание, образованное с помощью связки или
, ложно, — это случай, когда ложны обе части этого высказывания. Такая ситуация имеет место только в случаях 5, 6 и 8.
Другой, эквивалентный способ построения таблицы истинности состоит в том, чтобы записывать истинностные значения выражения под связкой. Снова рассмотрим выражение. Сначала мы записываем истинностные значения под переменными р
, q
и r
. Единицы под столбцами истинностных значений указывают на то, что этим столбцам истинностные значения присваиваются в первую очередь. В общем случае число под столбцом будет показывать номер шага, на котором производятся вычисления соответствующих истинностных значений. Затем мы записываем под символом ~ истинностные значения высказывания . Далее записываем истинностные значения под символом . Наконец, записываем значения высказывания под символом .
| Случай | p | q | r | p | ((~ | q ) | r | ||
| T | T | T | T | T | F | T | F | T | |
| T | T | F | T | T | F | T | F | F | |
| T | F | T | T | T | T | F | T | T | |
| T | F | F | T | T | F | F | F | F | |
| F | T | T | F | F | F | T | F | T | |
| F | T | F | F | F | F | T | F | F | |
| F | F | T | F | T | T | F | T | T | |
| F | F | F | F | F | F | F | F | F | |
1.1.3. Условные высказывания
Допустим, некто утверждает, что если случится одно событие, то случится и другое. Предположим, отец говорит сыну: "Если в этом семестре ты сдашь все экзамены на «отлично», я куплю тебе машину ". Заметьте, что высказывание имеет вид: если р, то q , где р — высказывание В этом семестре ты сдашь все экзамены на «отлично» , а q — высказывание Я куплю тебе машину . Сложное высказывание мы обозначим символически через . Спрашивается, при каких условиях отец говорит правду? Предположим, высказывания р и q истинны. В этом случае счастливый студент получает отличные оценки по всем предметам, и приятно удивленный отец покупает ему машину. Естественно, ни у кого не вызывает сомнения тот факт, что высказывание отца было истинным. Однако существуют еще три других случая, которые необходимо рассмотреть. Допустим, студент действительно добился отличных результатов, а отец не купил ему машину.
Самое мягкое, что можно сказать об отце в таком случае, — это то, что он солгал. Следовательно, если р истинно, а q ложно, то ложно. Допустим теперь, что студент не получил положительные оценки, но отец тем не менее купил ему машину. В этом случае отец предстает очень щедрым, но его никак нельзя назвать лжецом. Следовательно, если р ложно и q истинно, то высказывание если р, то q (т.е. ) истинно. Наконец, предположим, что студент не добился отличных результатов, и отец не купил ему машину.
Поскольку студент не выполнил свою часть соглашения, отец тоже свободен от обязательств. Таким образом, если р и q ложны, то считается истинным. Итак, единственный случай, когда отец солгал, — это когда он дал обещание и не выполнил его.
Таким образом, таблица истинности для высказывания имеет вид
Символ называется импликацией , или условной связкой .
Может показаться, что носит характер причинно-следственной связи, но это не является необходимым. Чтобы увидеть отсутствие причины и следствия в импликации, вернемся к примеру, в котором р есть высказывание Джейн управляет автомобилем , а q — утверждение У Боба русые волосы . Тогда высказывание Если Джейн управляет автомобилем, то у Боба русые волосы запишется как
если p , то q или как .
То, что Джейн управляет автомобилем, никак причинно не связано с тем, что Боб русоволосый. Однако нужно помнить, что истинность или ложность бинарного сложного высказывания зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой-либо связи.
Рассмотрим следующий пример. Требуется найти таблицу истинности для выражения
.
Используя таблицу истинности для , приведенную выше, построим сначала таблицы истинности для и , учитывая, что импликация ложна только в случае, когда .
Теперь используем таблицу для , чтобы получить для высказывания
таблицу истинности
| Случай | p | q | r | (p | q ) | (q | r ) | |||
| T | T | T | T | T | T | T | T | T | T | |
| T | T | F | T | T | T | F | T | F | F | |
| T | F | T | T | F | F | F | F | T | T | |
| T | F | F | T | F | F | F | F | T | F | |
| F | T | T | F | T | T | T | T | T | T | |
| F | T | F | F | T | T | F | T | T | F | |
| F | F | T | F | T | F | T | F | F | T | |
| F | F | F | F | T | F | T | F | T | F | |
| * |
Высказывание вида обозначается через . Символ называется эквиваленцией . Эквиваленция также иногда обозначается как (не следует путать с унарной операцией отрицания).
Лабораторная работа № 7-8
Алгебра логики
Цель работы: Изучить основы алгебры логики.
Задачи лабораторной работы
В результате прохождения занятия студент должен:
определения основных понятий (простое и сложное высказывания, логические операции, логические выражения, логическая функция);
порядок выполнения логических операций;
алгоритм построения таблиц истинности;
схемы базовых логических элементов;
законы логики и правила преобразования логических выражений;
применять загоны логики для упрощения логических выражений;
строить таблицы истинности;
строить логические схемы сложных выражений.
Общие теоретические сведения
Основные понятия алгебры логики
Логической основой компьютера является алгебра логики, которая рассматривает логические операции над высказываниями.
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Пример. «3 – простое число» является высказыванием, поскольку оно истинно.
Не всякое предложение является логическим высказыванием.
Пример. предложение «Давайте пойдем в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются.
Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Пример. «x+2>5» - высказывательная форма, которая при x>3 является истинной, иначе ложной.
Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками .
Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми).
Пример. высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и».
Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.
Чтобы обращаться к логическим высказываниям, им назначают имена.
Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 1).
Таблица 1. Основные логические операции
|
Обозначение операции |
Читается |
Название операции |
Альтернативные обозначения |
|
Отрицание (инверсия) |
Черта сверху |
||
|
Конъюнкция (логическое умножение) | |||
|
Дизъюнкция (логическое сложение) | |||
|
Если … то |
Импликация | ||
|
Тогда и только тогда |
Эквиваленция | ||
|
Либо …либо |
Исключающее ИЛИ (сложение по модулю 2) |
НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬). Высказывание ¬А истинно, когда A ложно, и ложно, когда A истинно.
Пример. Пусть А=«Сегодня пасмурно», тогда ¬А=«Сегодня не пасмурно».
И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « » (может также обозначаться знаками или &). Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны.
Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно.
ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком (или плюсом). Высказывание АВ ложно тогда и только тогда, когда оба высказывания А и В ложны.
Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно.
ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → или . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.
Пример. Высказывание «если студент сдал все экзамены на «отлично», то он получит стипендию». Очевидно, эту импликацию следует признать ложной лишь в том случае, когда студент сдал на «отлично» все экзамены, но стипендии не получил. В остальных случаях, когда не все экзамены сданы на «отлично» и стипендия получена (например, в силу того, что студент проживает в малообеспеченной семье) либо когда экзамены вообще не сданы и о стипендии не может быть и речи, импликацию можно признать истинной.
РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~ или . Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.
Пример: Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно.
ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание АВ истинно тогда и только тогда, когда значения А и В не совпадают.
Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на 3» – ложно, так как истинны оба высказывания входящие в него.
Замечание. Импликацию можно выразить через дизъюнкцию и отрицание:
Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:
Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию:
Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.
Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и исключающего или и в последнюю очередь – импликация и эквиваленция.
С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).
Логическая формула - это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).
Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.
Пример . – логическая функция двух переменных A и B.
Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности .
Приведем таблицу истинности основных логических операций (табл. 2)
Таблица 2
Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул.
Алгоритм построения таблиц истинности для сложных выражений:
количество строк = 2 n + строка для заголовка,
n - количество простых высказываний.
количество столбцов = количество переменных + количество логических операций;
определить количество переменных (простых выражений);
определить количество логических операций и последовательность их выполнения.
Пример 1. Составить таблицу истинности для формулы И–НЕ, которую можно записать так:.
1. Определить количество строк:
На входе два простых высказывания: А и В, поэтому n=2 и количество строк =2 2 +1=5.
2. Определить количество столбцов:
Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4.
3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 3).
Таблица 3. Таблица истинности для логической операции
Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так:
Таблица 4. Таблица истинности для логической операции
Примечание: И–НЕ называют также «штрих Шеффера» (обозначают |)
или «антиконъюнкция» ; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция» .
Пример 2. Составить таблицу истинности логического выражения .
Решение:
1. Определить количество строк:
На входе два простых высказывания: А и В, поэтому n=2 и количество строк=2 2 +1= 5.
2. Определить количество столбцов:
Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция), т.е. количество столбцов таблицы истинности = 7.
Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.
3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 5).
Таблица 5. Таблица истинности для логической операции
Логические формулы можно также представлять с помощью языка логических схем.
Существует три базовых логических элемента, которые реализуют три основные логические операции:
логический элемент «И» – логическое умножение – конъюнктор;
логический элемент «ИЛИ» – логическое сложение – дизъюнктор;
логический элемент «НЕ» – инверсию – инвертор.
Поскольку любая логическая операция может быть представлена в виде комбинации трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из “кирпичиков”.
Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции.
Преобразование сигнала логическим элементом задается таблицей состояний, которая фактически является таблицей истинности, соответствующей логической функции, только представлена в форме логических схем. В такой форме удобно изображать цепочки логических операций и производить их вычисления.
Алгоритм построения логических схем.
Определить число логических переменных.
Определить количество логических операций и их порядок.
Изобразить для каждой логической операции соответствующий ей логический элемент.
Соединить логические элементы в порядке выполнения логических операций.
Пример. По заданной логической функции построить логическую схему.
Решение.
Число логических переменных = 2 (A и B).
Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.
Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор.
Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов).
Логические законы и правила преобразования логических выражений
Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными .
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений.
1. Закон двойного отрицания: ;
2. Переместительный (коммутативный) закон:
3. Сочетательный (ассоциативный) закон:
4. Распределительный (дистрибутивный) закон:
5. Законы де Моргана:
6. Закон идемпотентности:
7. Законы исключения констант:
8. Закон противоречия:;
9. Закон исключения третьего: ;
10. Закон поглощения:
11. Правило исключения импликации: ;
12. Правило исключения эквиваленции: .
Справедливость этих законов можно доказать составив таблицу истинности выражений в правой и левой части и сравнив соответствующие значения.
Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Пример. Упростить логическое выражение .
Решение:
Согласно закону де Моргана:
Согласно сочетательному закону:
Согласно закону противоречия и закону идемпотентности:
Согласно закону исключения 0:
Окончательно получаем
/ Задания к лабораторной работе
Пример 1. Установите, какие из следующих предложений являются логическими высказываниями, а какие - нет (объясните почему):
а) “Солнце есть спутник Земли ”;
б) “2+3 =4 ”;
в) “сегодня отличная погода ”;
г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов ”;
д) “Санкт-Петербург расположен на Неве ”;
е) “музыка Баха слишком сложна ”;
ж) “первая космическая скорость равна 7.8 км/сек ”;
з) “железо - металл ”;
и) “если один угол в треугольнике прямой, то треугольник будет тупоугольным ”;
к) “если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный ”.
Пример 2. Укажите, какие из высказываний предыдущего упражнения истинны, какие - ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить.
Пример 3. Приведите примеры истинных и ложных высказываний:
а) из арифметики; б) из физики;
в) из биологии; г) из информатики;
д) из геометрии; е) из жизни.
Пример 4. Сформулируйте отрицания следующих высказываний или высказывательных форм:
а) “Эльбрус - высочайшая горная вершина Европы”;
б) “2>=5”;
в) “10<7”;
г) “все натуральные числа целые”;
д) “через любые три точки на плоскости можно провести окружность”;
е) “теннисист Кафельников не проиграл финальную игру”;
ж) “мишень поражена первым выстрелом”;
з) “это утро ясное и теплое”;
и) “число n делится на 2 или на 3”;
к) “этот треугольник равнобедренный и прямоугольный”;
л) "на контрольной работе каждый ученик писал своей ручкой".
Мы будем знакомиться с самым элементарным разделом логики - алгеброй высказываний.
Исходные объекты алгебры высказываний - это простые (элементарные) высказывания. Мы в дальнейшем будем их обозначать строчными латинскими буквами а, b, с, ..., х, у, z .
Предполагается, что всякое простое высказывание обладает одним и только одним из двух свойств: оно либо только истинно, либо только ложно. Внутри алгебры высказываний не говорится о том, что такое простое высказывание и что такое «истинность» и «ложность». Однако на первоначаоной стадии изучения этого раздела математики необходимо четко разобраться в том, что такое высказывание. Для этого рассмотрим ряд предложений и выясним какие из них являются высказыванием, а какие нет.
1. "Число 21 делится на 3";
2. "Тринадцать меньше пяти";
3. "Число 201 больше 180 на 21"
4. 1 это единственный корнь уравнения x 2 - 1 = 0";
Каждое из этих предложений содержит одно утверждение, которое не сложно проверить, выполнив ряд действий или рассуждений, т. е. можно установить истинность или ложность каждого утверждения. Первое и третье утверждения истинны, второе и четвертое ложны. Это примеры высказываний.
Всякое высказывание является предложением, но далеко не каждое предложение является высказыванием. Вот примеры предложениий, которые высказываниеми не являются.
1. "Аристотель - грек";
2. "Число 0,00001 очень мало";
3. "x больше 3";
4. "2x + 3 =17";
5. "Существует ли рациональное число квадрат которого равен 2?"
Первое и второе предложения неопределенны и нуждаются в дополнительных пояснениях. В первом предложении однозначно сказать, что речь идет об основателе формальной логики, а ни ком-то другои, нельзя. Во втором случае величина числа зависит от рассматриваемой ситуации, в одних случаях это число действительно может оказаться очень малым, а вдругих нет. Третье и четвертое предложения содержат переменную и, следовательно, неопределены. Выяснить истинны они или нет нельзя до тех пор пока не будут известны значения переменной. Пятое предложение вообще ничего не утверждает и поэтому бессмысленно о говорить об истинности или ложности этого предложения.
1. "Число 30221 157 + 5342 345623 + 1 является простым числом";
В первом примере для того чтобы выяснить ложность или истинность утверждения нужно выполнить очень большое количество действийи на это прийдется затратить много времени и средств, по теоретически (формально) установить истинность или ложность этого утверждения млжно. Во втором примере в данный момент установить истинность утверждения невозможно, но наступит момент, когда проверка истинности или ложности предложения в общем случае будеь возможна. Поэтому считают, что такие предложения также являются высказываниями.
Вообще, многие математические утверждения можно считать простыми высказываниями при этом принято считать, что они либо истинны, либо ложны, даже если нам неизвестно, каким из двух свойств данное высказывание обладает. Так, например, «Всякое четное число является суммой двух простых чисел» - высказывание, хотя мы не знаем, каким из двух свойств оно в действительности обладает: это нерешенная проблема Гольдбаха.
Когда речь идет о высказывании нужно иметь в виду следующее:
1. Любое высказывание является либо истинным, либо ложным (закон исключенного третьего).
2. Никакое высказывание не может быть одновременно истинным и ложным (закон противоречия).
3. Предложение, о котором невозможно однозначно решить вопрос, истинно оно или ложно, высказыванием не является.
Алгебра логики не занимается обоснованием того, почему, тому или иному прлстому (элементарному) высказыванию присваевается значение истинности или ложности, этим занимаются другие разделы математики или науки. Более того алгебра логики отвлекается от смысловой содержательности высказываний, ее интересуют только их значения (истинно или ложно). Такой подход позволяет строить и изучать как угодно сложные (составные) высказывания. Истинность или ложность сложных высказывания зависит ни от каких-то внешних причин, а от простых высказываний и логических связок из которых составлено это сложное высказывание.
Из простых высказываний с помощью небольшого числа операций строятся сложные высказывания. Операции, называемые логическими связками или логическими функциями, примерно соответствуют тому, что в обыденной речи описывается словами «не», «и», «или», «если..., то» и т. п.
Сложные высказывания также обладают одним из двух свойств: «быть истинным» или «быть ложным». При этом истинность или ложность сложного высказывания зависит исключительно от истинности или ложности простых высказываний, из которых они с помощью связок получаются и логической опрерации испрльзуемой в составлении сложного высказывания.
В дальнейшем мы будем пользоваться, почти повсеместно принятой терминологией: свойства истинности обозначать и и ложности обозначать л . Также в дальнейшем мы будем и и л называть значениями истинности высказываний: и - является значением истинности истинных высказываний, а л есть значение истинности ложных высказываний. При такой терминологии значение истинности сложного высказывания есть функция от значений истинности простых высказываний; такая функция называется логической связкой. Связка полностью может быть описана таблицей, указывающей, какие значения истинности принимает сложное высказывание при различных значениях истинности простых. Такая таблица называется матрицей истинности (или иногда таблицей истинности), соответствующей данной связке.
1. Отрицание. Эту логическую связку мы будем обозначать a . Если а - высказывание, то а (читается: «не а») также высказывание; оно истинно или ложно в зависимости от того, ложно или истинно высказывание а.
Таким образом, операция отрицания описывается следующей таблицей:
Мы видим, что операция в теории высказываний вполне соответствует понятию отрицания в обыденном смысле слова. Если, например, а - высказывание «Число три делит число шесть», то отрицанием a этого высказывания будет «Число три не делит число шесть». Высказывание а при этом истинно, высказывание a - ложно. Если же в качестве высказывания а взять какое-нибудь ложное высказывание, например «Число три делит число пять», то его отрицание a будет высказывание «Число три не делит число пять» - истинное высказывание.
2. Конъюнкция.
В качестве знака для конъюнкции мы будем
употреблять знак -&
Если, а и b - высказывания, то а&b (читается: «а и b») - новое высказывание; оно истинно тогда и только тогда, когда а истинно и b истинно. В отличие от операции отрицания, зависящей от одного элементарного высказывания, конъюнкция, как и все последующие приводимые нами связки, зависит от двух элементарных высказываний, поэтому они называются двуместными связками, отрицание же - связка одноместная.
Для задания двуместных связок удобно записывать матрицы истинности в виде таблиц с двумя входами: строки соответствуют значениям истинности одного элементарного высказывания, столбцы - значениям другого элементарного высказывания, а в клетке пересечения столбца и строки помещается значение истинности соответствующего сложного высказывания.
Как видно, определение операции конъюнкции вполне соответствует обыденному значению союза «и».
3. Дизъюнкция. В качестве знака для дизъюнкции мы будем употреблять знак V
Если а и b - высказывания, то а V b (читается: «а или b») - новое высказывание, оно ложное, если а и b ложны; во всех остальных случаях а V b истинно.
Таким образом, таблица истинности для операции дизъюнкции выглядит так:
Операция дизъюнкции довольно хорошо соответствует обыденному значению союза «или». Детальный анализ показывает, что в русском языке слово «или» употребляется в двух различных значениях: существуют исключающее «или» и неисключающее «или». Различие состоит в следующей: пусть а и b - два истинных высказывания, например а - «Число три делит число шесть», b - «Число шесть большее чем число три». Следует ли рассматривать сложное высказывание а V b - «Число три делит число шесть или число шесть больше, чем число три» как истинное или как ложное? В обыденной русской речи встречаются оба понимания: утверждение «а или b» может означать, что одно и только одно из предложений а и b истинно, тогда говорят, что слово «или» употребляется в исключающем смысле, или же «а или b» означает, что истинно по меньшей мере одно из предложений (но могут быть истинны оба), в этом случае говорят, что «или» употребляется в неисключающем смысле. Именно неисключающему «или» и соответствует дизъюнкция. Исключающему «или» соответствует, очевидно, таблица истинности
А в неисключающем смысле:
«Три делит пять или три больше шести» ложно;
«Три делит шесть или три больше шести» истинно;
«Три делит шесть или три меньше шести» истинно.
3. Импликация. В качестве знака для импликации будем употреблять знак,
Если а и b - два высказывания, то аb (читается: «а имплицирует b») - новое высказывание; оно всегда истинно, кроме того случая, когда а истинно, a b ложно. Таблица истинности операции импликации следующая:
В импликации аb первый член а называется антецедентом, второй b - консеквентом. Операция описывает в некоторой мере то, что в обыденной речи выражается словами «Если а, то b», «Из а следует b», «a - достаточное условие для b», но на этой аналогии не следует слишком настаивать. Действительно, учитывая определение импликации, данное выше, и интерпретируя выражение аb как «если а, то b», мы получаем: «Если дважды два - четыре, то трижды три - девять» - истинное высказывание; «Если дважды два - пять, то трижды три - восемь» - истинное высказывание и только высказывание типа «Если дважды два - четыре, то трижды, три - восемь» ложно.
По определению импликации сложное высказывание аb всегда истинно, если консеквент истинный или если антецедент ложный, что в очень малой мере отражает обыденное значение выражения «Если а, то b» или «Из а следует b». Ни в какой мере не следует рассматривать высказывание импликации как означающее, что антецедент является причиной, а консеквент - следствием в том смысле, как это понимается в естественных науках.
Несколько позже мы убедимся, что операция импликации достаточно точно выражает понятие логического следования в той форме, как оно употребляется в математике.
4. Эквиваленция.
Для. этой операции мы будем употреблять знак . Операция эквиваленции определяется так: если а и b - два высказывания, то аÛ
b (читается: «а эквивалентно b»; соответствует словесному выражению «...тогда и только тогда, когда...» - новое высказывание, которое истинно, если либо оба высказывания истинны, либо оба - ложны. b (читается: «а меньше или равно b) представляет собой дизъюнкцию (а < b)V(a = b) оно истинно, если истинно по меньшей мере одно из входящих в него простых высказываний. Хорошими примерами сложных высказываний, встречающихся в школьной практике, являются так называемые двойные неравенства. Так, формула а < b < с означает
(а < b) & (b < с), а, например,
а < bс означает сложное высказывание (а < b)& ((b < c)V(b = с)).
Делается это аналогично тому, как в элементарной алгебре с помощью операций сложения, вычитания, умножения и деления строятся сколь угодно сложные рациональные выражения. А именно, предположим, что мы уже построили два каких-нибудь сложных высказывания, которые мы ради удобства сокращенно обозначим большими латинскими буквами А и В (при этом мы условимся, что элементарные высказывания следует рассматривать как частный случай сложных). Тогда новые высказывания можно получить, соединив А и В одрим из знаков & , V, , или же построив высказывание A и заключив результат в скобки. Сложными высказываниями будут, например, высказывания следующего вида:
((а b) & (с V а));
((аb) (с а )).
При этом предполагается, что встречающиеся здесь буквы являются сокращенными обозначениями каких-либо высказываний. Таким образом, в принципе зная эти высказывания, можно было бы построить русские фразы, выражающие эти сложные высказывания. Только словесное описание сложных высказываний быстро становится малообозримым, и именно введение целесообразной символики позволяет проводить более глубокое и точное исследование логических связей, между различными высказываниями.
Располагая значением истинности простых высказываний, легко подсчитать на основании определения связок значение истинности сложного высказывания. Пусть, например, дано сложное высказывание
(a V с)(b&
а))
и пусть входящие в него элементарные высказывания имеют следующие значения истинности: а = л, b = и, с = и. Тогда b V с = и, b &
а = л, так что (a V с)(b &
а) = л, т. е. рассматриваемое высказывание ложно.
Алгебра в широком смысле этого слова - наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над разнообразными математическими объектами.
Многие математические объекты (целые и рациональные числа, многочлены, векторы, множества) вы изучаете в школьном курсе алгебры, где знакомитесь с такими разделами математики, как алгебра чисел, алгебра многочленов, алгебра множеств и т. д. Для информатики важен раздел математики, называемый алгеброй логики
; объектами алгебры логики являются высказывания
.
Высказывание
- это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
Пример:
Например, относительно предложений «Великий русский учёный М. В. Ломоносов родился в \(1711\) году» и «Two plus six is eight» можно однозначно сказать, что они истинны. Предложение «Зимой воробьи впадают в спячку» - ложно. Следовательно, эти предложения являются высказываниями.
В русском языке высказывания выражаются повествовательными предложениями.
Обрати внимание!
Но не всякое повествовательное предложение является высказыванием.
Пример:
Например, предложение «Это предложение является ложным» не является высказыванием, так как относительно него нельзя сказать, истинно оно или ложно, без того чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит сказанному. Если же принять, что предложение ложно, то отсюда следует, что оно истинно.
Побудительные и вопросительные предложения высказываниями не являются.
Например, не являются высказываниями такие предложения, как: «Запишите домашнее задание», «Как пройти в библиотеку?», «Кто к нам пришёл?».
Высказывания могут строиться с использованием знаков различных формальных языков - математики, физики, химии и т. п.
Примерами высказываний могут служить:
«Nа - металл» (истинное высказывание);
«Второй закон Ньютона выражается формулой \(F = ma\) (истинное высказывание);
«Периметр прямоугольника с длинами сторон \(а\) и \(b\) равен \(аb\)» (ложное высказывание).
Не являются высказываниями числовые выражения, но из двух числовых выражений можно составить высказывание, соединив их знаками равенства или неравенства. Например:
- 3 + 5 = 2 ⋅ 4 (истинное высказывание);
- «II + VI > VIII» (ложное высказывание).
Не являются высказываниями и равенства или неравенства, содержащие переменные.
Например, предложение \(«x < 12»\) становится высказыванием только при замене переменной каким-либо конкретным значением: \(«5 < 12»\) - истинное высказывание; \(«12 < 12»\) - ложное высказывание.
Обоснование истинности или ложности высказываний решается теми науками, к сфере которых они относятся. Алгебра логики отвлекается от смысловой содержательности высказываний. Её интересует только то, истинно или ложно данное высказывание. В алгебре логики высказывания обозначают буквами и называют логическими переменными . При этом, если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей \((А = 1)\), а если ложно - нулём \((В = 0)\).
\(0\) и \(1\), обозначающие значения логических переменных, называются логическими значениями .