Что такое логическая формула

Введение

Я выбрал тему учебно-методического комплекса «Логика», так как она является одной из главной тем в информатике, к тому же логика необходима во множестве точных наук.
Что такое алгебра логики

Создателем алгебры логики является живший в XIX в. анг­лийский математик Джордж Буль, в честь которого она названа бу левой алгеброй высказываний.

 Так, например, предложение «6 — четное число» следует счи­тать высказыванием, так как оно истинное. Предложение «Рим — столица Франции» тоже высказывание, так как оно ложное.

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

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. За­метим, что зачастую трудно установить истинность высказывания. Так, например, высказывание «площадь поверхности Индийского океана равна 75 млн км²» в одной ситуации можно посчитать лож­ным, а в другой — истинным. Ложным — так как указанное зна­чение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

Употребляемые в обычной речи слова и словосочетания «не», «и», или», «если „., то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Так, например, из элементарных высказываний «Петров — врач», «Петров — шахматист» при помощи связки «и» можно полу­чить составное высказывание «Петров - врач и шахматист», понима­емое как «Петров — врач, хорошо играющий в шахматы».

При помощи связки «или» из этих же высказываний можно получить составное высказывание «Петров — врач или шахматист», понимаемое в алгебре логики как «Петров или врач, или шахматист, или и врач и шахматист одновременно».

Истинность или ложность получаемых таким образом состав­ных высказываний зависит от истинности или ложности элементар­ных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание «Тимур поедет летом на море», а через В — высказывание «Тимур летом отправится в горы». Тогда составное высказывание «Тимур летом побывает и на море, и в горах» можно кратко записать как А и В. Здесь «и» — логическая связка, А, В — логические переменные, которые могут принимать только два значения - «истина» или «ложь», обозначае­мые соответственно «1» и «О».

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

Операция, выражаемая словом «не», называется отрицанием и обозна­чается чертой над высказыванием (или знаком 1). Высказывание А истинно, когда А ложно, и ложно, когда А истинно. Например,

«Луна - спутник Земли» (А); «Луна — не спутник Земли» (А).

Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой • (может обозначаться знаком ^ или &). Высказывание А-В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание «10 делится на 2 и 5 больше 3» истинно, а высказывания «10 делится на 2 и 5 не больше 3», «10 не делится на 2 и 5 больше 3», «10 не делится на 2 и 5 не больше 3» ложны.

Операция, выражаемая связкой «или» (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание AvB ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание «10 не делит­ся на 2 или 5 не больше 3» ложно, а высказывания «10 делится на 2 или 5 больше 3», «10 делится на 2 или 5 не больше 3», «10 не делится на 2 или 5 больше 3» истинны.

Операция, выражаемая связками «если ..., то», «из ... следует», «... влечет ...», называется импликацией (лат. implico — тесно свя­заны) и обозначается знаком ->. Высказывание А-»В ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементар­ных высказывания? Покажем это на примере высказываний: «дан­ный четырехугольник — квадрат» (А) и «около данного четырехуголь­ника можно описать окружность» (В). Рассмотрим составное высказывание А—>В, понимаемое как «если данный четырехугольник — квадрат, то около него можно описать окружность». Есть три вари­анта, когда высказывание А—>В истинно:

А истинно и В истинно, т. е. данный четырехугольник — квадрат, и около него можно описать окружность;

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

Ложен только один вариант: А истинно и В ложно, т. е. данный четырехугольник является квадратом, но около него нельзя описать окружность.

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

Операция, выражаемая связками «тогда и только тогда», «необходимо ■ достаточно», «... равносильно ...», называется эквиваленцией или двойствен ной импликацией и обозначается знаком <-> или ~ . Высказывание А <-» В истинно тогда и только тогда, когда значения А и В совпа­ дают. Например, истинны высказывания:

«24 делится на 6 тогда и только тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» — и ложны высказывания:

«24 делится на 6 тогда и только тогда, когда 24 делится на 5», «21 делится на 6 тогда и только тогда, когда 21 делится на 3».

Высказывания А и В, образующие составное высказывание А<-»В, могут быть совершенно не связаны по содержанию, например: «три больше двух» (А), «пингвины живут в Антарктиде» (В). Отрица­ниями этих высказываний являются высказывания «три не больше двух» (А), «пингвины не живут в Антарктиде» (В). Образованные из высказываний А, В составные_ высказывания А<->В и А <-» В истинны, а высказывания А<-»В и А<-»В ложны.

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

Импликацию можно выразить через дизъюнкцию и отрицание:                                                                                 А  >В =А vB   Эквиваленцию можно выразить через о трицание, дизъюнкцию и конъюнкцию:                                  А<->В = (А vB) *(В v А).

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

Порядок выполнения логических операций задается круглы­ми скобками. Но для уменьшения числа скобок договорились счи­тать, что сначала выполняется операция отрицания («не»), затем — конъюнкция («и»), после конъюнкции — дизъюнкция («или») и в последнюю очередь — импликация.

Что такое логическая формула

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

Всякаялогическая переменная и символы «истина» («1») и «ложь» («О») — формулы.

БетаА и В - формулы, то А , (А • В), (AvB), (A->B), (А<->В) - формулы. Никаких других формул в алгебре логики нет.

В пункте 1 определены элементарные формулы , в пункте 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог». Это вы­сказывание формализуется в виде (AvB)-> С; такая же формула со­ответствует высказыванию «если Игорь знает английский или япон­ский язык, то он получит место переводчика».

Как показывает анализ формулы (A v В) —» С, при опреде­ленных сочетаниях значений переменных А, В и С она принимает значение «истина», а при некоторых других сочетаниях — значение «ложь» (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

Некоторые формулы принимают значение «истина» при лю­бых значениях истинности _входящих в них переменных. Такой бу­дет, например, формула A v A , соответствующая высказыванию «этот треугольник прямоугольный или косоугольный». Эта формула истин­на и тогда, когда треугольник прямоугольный, и тогда, когда тре­угольник непрямоугольный. Такие формулы называются тождествен­ но-истинными формулами или тавтологиями.

Высказывания, которые формализуются тавтологиями, назы­ваются логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А • А , ко­торой соответствует, например, высказывание «Катя — самая высо­кая девочка в классе, и в классе есть девочки выше Кати». Очевид­но, что эта формула ложна, так как либо А, либо А обязательно ложно. Такие формулы называются тождественно-ложными формулами или противоречиями.

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

Если две формулы А и В одновременно, т. е. при одина­ковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Равносильность двух формул алгебры логики обозначается символом «=» или символом «=». Замена формулы другой, ей равно­сильной, называется равносильным преобразованием данной формулы.