Что называется формулой логики высказываний

Что называется формулой логики высказываний

Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1) любая высказывательная переменная – формула;

3) только те слова являются формулами, для которых это следует из 1) и 2).

Например: или . Скобки указывают порядок выполнения действий.

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

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

При x = 1, y = 1, z = 0 формула

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

Таблица истинности логических значений формулы будет следующая:

Если формула содержит n элементарных высказываний, то она принимает 2 n значений. Таблица истинности будет содержать 2 n строк.

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

Следующие формулы являются равносильными:

Формула А называется тождественно истинной (или тавтологией ), если она принимает значение 1 при всех значениях входящих в нее переменных.

Следующие формулы являются тавтологиями: ,

Формула является тождественно ложной.

Отношение равносильности обладает следующими свойствами: оно рефлексивно, симметрично и транзитивно.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула – тавтология, и обратно, если формула – тавтология, то формулы А и В равносильны.

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

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности

Пусть А ≡ при x = 1, значение А = 1, при х = 0, значение А = 0. Итак во всех случаях значения формулы А совпадают со значениями х, следовательно, А ≡ х.

2. Равносильности, выражающие одни логические операции через другие

Замечание. Формулы 5 и 6 получаются из 3 и 4, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

Докажем формулы 1–4.

1) при одинаковых логических значениях x и y формулы , и – истинны, следовательно, истинной будет и коньюнкция т. е. обе части равносильности имеют одинаковые истинные значения.

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

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

Аналогично доказываются равносильности 2 и 4.

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

3. Равносильности, выражающие основные законы алгебры логики

– комм утативность коньюнкции и дизьюнкции.

При х = 1, формулы , и будут истинны, тогда и – тоже истинна.

При х = 0, ≡ , ≡ ≡ следовательно,

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

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

1) раскрытие скобок;

2) заключение в скобках;

3) вынесения за скобки общего множителя.

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

Равносильные преобразования формул используют

1) для доказательства равносильностей,

2) для приведения формул к заданному виду,

3) для упрощения формул.

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

1. Доказать равносильность

2. Упростить формулу

3. Доказать тождественную истинность формулы

Источник

Конспект по элементам математической логики на тему «Формулы логики высказываний»

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Формулы логики высказываний

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

Выражение, составленное из обозначений высказываний, логических связок и скобок, называется логической формулой, если оно удовлетворяет следующим условиям:

— любая переменная, обозначающая высказывание, является формулой ;

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

Л ишние скобки опускаются.

Порядок построения формул логики высказываний на основе сложных высказываний:

1. Разложить сложное высказывание на простые высказывания.

2. Каждому простому высказыванию назначить соответствующую логическую переменную.

3. Определить логические операции над простыми высказываниями.

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

Рассмотрим примеры представления логическими формулами следующих высказываний.

Высказывание: «Идет дождь или снег».

Логической операции, соответствующей логической связке «или», является дизъюнкция ( Ú ). Л огическая формула примет вид:

Высказывание: «Сегодня суббота или воскресенье».

Составное высказывание «Сегодня суббота или воскресенье» состоит из двух простых высказываний :

Л огическая формула примет вид:

Высказывание: «Что с горы, что под гору».

Высказывание « Что с горы, что под гору », разобьем на два простых высказывания и введем обозначения:

Два высказывания соединены операцией эквивалентности (↔). Высказывание « Что с горы, что под гору » представимо логической формулой :

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

Высказывание: «Если идет дождь, то пикник отменяется. Дождя нет, но пикник отменяется ».

Сложное высказывание включает два простых высказывания:

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

Во втором предложении («Дождя нет, но пикник отменяется ») союз «но» имеет смысл связки «и» (конъюнкция &).. Для фразы «нет дождя» к высказыванию А необходимо применить операцию отрицания ( ):

.

Далее объединим представленные выше два высказывания в одно связкой &:

.

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

Составное высказывание состоит из следующих простых высказываний:

D — « Необходимо убедиться в необходимости их применения в проекте ».

Логическая формула второго составного высказывания:

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

Первое составное высказывание состоит из следующих простых высказываний:

В — « Вы используете калькулятор ».

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

Первое предложение содержит следующие простые высказывания:

D — «Для фирмы рациональной является стратегия экономии издержек»

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

Второе предложение содержит другие простые высказывания:

L — «Интенсивный маркетинг является слабой стороной организации».

Логическая формула, представляющая второе предложение:

В третьем предложении содержатся новые простые высказывания:

N — «Фирме следует придерживаться стратегии захвата новых рынков для определенного продукта».

Логическая формула для третьего предложения:

Окончательно составное высказывание записывается следующей логической формулой:

((А&В) ® (С ↔ D ))&((К& L ) ® (С ↔ D ))&((К&М) ® N ).

Упражнения для самостоятельной работы.

Представить логическими формулами следующие высказывания:

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

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Источник

Что называется формулой логики высказываний

8. ЛОГИКА ВЫСКАЗЫВАНИЙ

8.1. Основы логики высказываний

Пример: Если посещать все занятия по «Представлению знаний в ИС», то можно получить автомат за экзамен. Петров присутствовал на всех занятиях по «Представлению знаний в ИС». Следовательно, он получит автомат.

Пример: Если посещать все занятия по «Представлению знаний в ИС», то можно получить автомат за экзамен. Петров не получил автомат. Следовательно, он пропускал занятия по «Представлению знаний в ИС».

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

Примеры неправильных модусов.

Если посещать все занятия по «Представлению знаний в ИС», то можно получить автомат за экзамен. Петров получил автомат. Следовательно, он не пропускал занятия по «Представлению знаний в ИС». На самом деле возможна другая причина получения автомата.

Если посещать все занятия по «Представлению знаний в ИС», то можно получить автомат за экзамен. Петров пропускал занятия по «Представлению знаний в ИС». На самом деле он получил автомат, но за другие заслуги.

Мы будем посещать все занятия по «Представлению знаний в ИС» или придется сдавать экзамен. Да, мы будем посещать все занятия по «Представлению знаний в ИС». Следовательно, есть надежда на автомат.

Мы будем посещать все занятия по «Представлению знаний в ИС» или придется сдавать экзамен. Мы будем пропускать занятия по «Представлению знаний в ИС». Следовательно, придется сдавать экзамен.

Мы будем посещать все занятия по «Представлению знаний в ИС» или придется сдавать экзамен. Есть надежда на автомат. Следовательно, мы будем дальше посещать все занятия по «Представлению знаний в ИС».

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

8.2. Синтаксис и семантика логики высказываний

В логике высказываний используется следующий синтаксис (символы):

— логические константы – ИСТИНА (И, TRUE, T) и ЛОЖЬ (Л, FALSE, F);

— атомарные высказывания (атомарные формулы, атомарные выражения, атомарные предложения) – обозначаются через прописные буквы латинского алфавита A, B, C и т.д. Например, «Земля вращается вокруг Солнца» (атомарное высказывание, выраженное на естественном языке) можно выразить через А. Атомарные высказывания относятся к константам и могут принимать только значения либо истина либо ложь;

— логические связки (операции, соединители):

— ∨ – логическое ИЛИ (дизъюнкция, логическое сложение);

Приоритет операций при исчислении формул показан ниже

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

— пропозициональные (логические) переменные – обозначаются через строчные буквы латинского алфавита p, q, r, x, y, z и т.д. Переменные соответствуют атомарным высказываниям или набору высказываний, связанных логическими операциями. Например, пусть дана формула A ∧ (B ∨ C). Тогда ее можно представить через переменные следующим образом:

— p – p соответствует A ∧ (B ∨ C);

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

Семантика логики высказываний (основные определения).

Правильно построенная формула (формула, ППФ) – одно или несколько высказываний (переменных), соединенных логическими операциями. Результат вычисления формулы истина или ложь. Примеры неправильно построенных формул: A ∨ B →, ¬A ¬∨ C, ↔ A ∧ B и т.д.

Противоречие (невыполнимая формула) – ППФ, значением которой всегда является ложь. Например, A ∧ ¬A.

Выполнимая формула – ППФ, значением которой может быть истина или ложь.

Тавтология – ППФ, значением которой всегда является истинна. Например, A ∨ ¬A. Некоторые тавтологии называют общезначимыми формулами (законами логики высказываний), т.к. они имеют фундаментальное значение и используются при исчислении высказываний. Перед общезначимыми формулы часто ставят знак ╞. Наиболее известными являются следующие законы:

— A ∧ (B ∨ С) ↔ (A ∧ B) ∨ (A ∧ С);

— A ∨ (B ∧ С) ↔ (A ∨ B) ∧ (A ∨ С);

— закон двойного отрицания:

8.3. Исчисление высказываний

Логическим исчислением (исчислением) называют совокупность, которая включает в себя [29]:

— алфавит (совокупность используемых символов);

— синтаксические правила построения формул;

— аксиомы – общезначимые формулы;

— правила вывода по аксиомам производных формул или теорем.

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

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

Выводом в теории Т называется всякая последовательность формул ППФ₁, ППФ₂, …, ППФ_i такая, что для любого i формула ППФ_i есть либо аксиома теории T, либо непосредственное следствие каких-либо предыдущих формул. Факт выводимости одной формулы из других показывается с помощью знака ├. Например, ППФ₁, …, ППФ_k ├ ППФ_m.

Классическое исчисление высказываний использует два правила вывода.

Правило 1. Modus Ponens – A, A → B ├ В. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации.

Правило 2. Правило подстановки – ППФ(р) ├ ППФ(Р). Из формулы ППФ(р) выводима формула ППФ(Р), получающаяся подстановкой формулы P вместо каждого вхождения переменной р.

Вопросы для самопроверки

1. Дайте определение понятию «высказывание».

Источник