Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





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

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

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.

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

Итак, пусть i│i I}— некоторое множество логических переменных. Определим по индукции понятие формулы алгебры высказываний (АВ):

1) любая логическая переменная является формулой АВ
(называемой атомарной);

2) если φ и ψ — формулы АВ, то выражения φ, (φ∧ψ),
(φ∨ψ), (φ→ψ)
являются формулами АВ;

3) никаких других формул АВ, кроме построенных по пп. 1 и 2, нет.

Если формула φ АВ построена из логических переменных, принадлежащих множеству 12,…,xn}, то будем писать φ(x1,…xn).

Символы , ∧, ∨ →, использованные в определении, называются логическими операциями или связками и читаются соответственно: отрицание, конъюнкция, дизъюнкция и импликация.

Эти логические операции следующим образом интерпретируются в русском языке: φ — "не φ", (φ∧ψ) — φ и ψ, (φ ψ) — φ или ψ, ( φ → ψ) — если φ, то ψ.

Вместо φ часто пишут , вместо ( φ∧ ψ) — (φ& ψ), (φ • ψ) или (φψ).

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

 

φ φ

 

φ ψ (φ ∧ ψ) (φ ∨ ψ) (φ → ψ)

Пример 1. Построить таблицу истинности для формулы φ ((x→y)∧((y→z)→x)).

Решение.Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы φ:

 

x y z (x→y) (y→z) ((y→z)→x) φ

 

Легко заметить, что таблица истинности для φ совпадает с таб­лицей истинности для x. В дальнейшем выяснится причина этого совпадения.

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

1. Внешние скобки не пишутся. Например, вместо высказывания ((x∨ y)→z) пишется (x∨ y)→z.

2. На множестве {, ∧, ∨, →} вводится транзитивное отношение "быть более сильным" следующим образом: наиболее сильная связка – , далее идут и , самая слабая связка – →.

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

Пример 2. В формуле ((x∨ y)→z)→u)) все скобки можно опустить: х∨ y→z→u.

 






Дата добавления: 2014-11-10; просмотров: 240. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.008 сек.) русская версия | украинская версия