Язык логики высказываний

Оглавление

 

4. Язык логики высказываний 8

Заключение 11

Задание 1 12

Задание 2 13

Список использованной литературы 14

 

Введение

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

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

Алфавит исчисления высказываний состоит из символов трех категорий:

1) Символы первой категории: x, y, z,…,x₁, x₂,…, которые называются переменными высказывания;

2)  Символы второй категории:  , которые называются логическими связками.   – дизъюнкция (логическое сложение),   – конъюнкция (логическое умножение), → – импликация (логическое следование), ¯ – отрицание;

3)   Символы третьей категории: скобки.

Других символов исчисление высказываний не имеет.

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

Цель данной работы –  изучить исчисление высказываний.

 

 

 

 

 

 

 

 

1. Пропозиционная  логика

 

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

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

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

1. Если P - пропозициональная переменная, то P - формула.
2. Если A - формула, то   - формула.
3. Если A и B - формулы, то  ,   и   - формулы.
4. Других формул нет.

 

 

 

 

 

 

 

 

 

 

 

 

2. Общезначимость  исчисления высказываний

 

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

Дана формула А. Является ли она  тавтологией или нет, можно определить, рассмотрев ее истинностную таблицу. Если простые компоненты, входящие в А, суть  , то А представляет собой тавтологию тогда и только тогда, когда ее истинностное значение есть Т при каждом из   приписанных   распределений значений Т и F. Например,   и   являются тавтологиями, тогда как   - не тавтология. Этот вывод основывается на рассмотрении помещенных ниже таблиц:

 

Теорема. Пусть В есть некоторая формула, а   - формула, получаемая из В подстановкой формулы А вместо простого компонента P везде, где он встречается в В. Тогда, если B – тавтология, то   - также тавтология.

Пример: 

Подставим вместо P: 

 

 

3. Пропорциональные связки

 

Знаки   и   (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. 

Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

Конъюнкция (от лат. conjunctio союз, связь) - логическая операция, по своему применению максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И».

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

,

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

Дизъюнкция (лат. disjunctio - разобщение), логическое сложение, логическое ИЛИ, включающее ИЛИ; иногда просто ИЛИ -логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».

Дизъюнкция может быть бинарной операцией (иметь два операнда), тернарной операцией (иметь три операнда) или  -арной операцией (иметь   операндов).

Запись может быть префиксной - знак операции стоит перед операндами (польская запись), инфиксной - знак операции стоит между операндами или постфиксной - знак операции стоит после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее.

Чаще всего встречаются  следующие варианты записи:

 

 ||   |  .

Импликация (лат. implicatio - связь) - бинарная логическая связка, по своему применению приближенная к союзам «если… то…».

Импликация записывается как посылка   следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие).

Суждение, выражаемое импликацией, выражается также следующими способами:

-посылка является условием, достаточным для выполнения следствия;

-следствие является условием, необходимым для истинности посылки.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Язык логики  высказываний

 

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

Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное логическое высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, - буквой Л. Тогда формулы первого уровня - это элементарные высказывания, к которым применена только одна логическая связка.

Пусть Ф1 и Ф2 - формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1) (Ф2)), ((Ф1) (Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

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

Например, пусть элементарными  высказываниями являются А, В, С. Записи

¬ A

 BC и (B) (B A→C)

c формальной точки  зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи

(¬ A)

(B C) и B ((B A)→C)

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

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

-Если опущены внешние скобки, то они восстанавливаются.

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

Если рядом стоят  разные связки, то скобки расставляются  согласно приоритетам:   и   (от высшего к низшему).

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись   означает формулу  , а её длина равна 12.

Интерпретацией (моделью) языка логики высказываний называется функция из множества всех пропозициональных переменных в множество истинностных значений {0, 1}. Основной задачей логики высказываний является установление истинностного значенияформулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок.

Оценка отрицания   задаётся таблицей:

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

 

 

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

Законы де Моргана:

1) 

;

2) 

;

Закон контрапозиции:

;

Законы поглощения:

1) 

;

2) 

;

Законы дистрибутивности:

1) 

;

2) 

.

 

 

 

 

 

 

 

Заключение

 

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

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

 

 

 

 

 

 

 

Задание 1

 

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

 

Решение:

Антецедент есть дизъюнкция предложений L (рабочие упорствуют) и М (администрация упорствует).

Консеквент есть эквиваленция, левая часть которой есть S (забастовка будет урегулирована), а правая часть есть конъюнкция предложения G (правительство добьется судебного запрещения) и отрицания предложения R (администрация не будет упорствовать).

Итак, приведённое выше предложение может быть символически записано так: