рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Формулы алгебры высказываний - раздел Информатика, ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ Высказыванием Называется Повествовательное Предложение, О Котором В Да...

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

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

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 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.

 

2.1.2. Логическое следствие в алгебре высказываний

 

Говорят, что формула ψ(х1,...,хп) АВ является логическим следствием формул φ11,...,хп),…,φm1,...,хп) АВ (обозначается ), если для любых из соотношений следует . Формулы называются гипотезами.

Пример 3. Доказать, что φ, φ→ψ, ψ→χ

Построим таблицы истинности для каждой формулы:

 

φ ψ χ φ→ψ ψ→χ

 

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

Формула φ(x1,x2,…,xn) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0) .

Пример 4. Формула х∧ у является одновременно выполнимой и опровержимой, поскольку 0∧0=0, а 1∧1=1.

Формула φ(x1,…,xn) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) на всех наборах значений переменных.

Пример 5. Формула x∨¬x является тождественно истинной, а формула x∧¬x — тождественно ложной:

 

 

x x∨¬x x∧¬x

 

Множество формул φ1,…,φn АВ называется противоречивым или несовместным, если формула φ1∧…∧φn тождественно ложна.

Пример 6.Множество формулx∨y, ¬x, ¬y противоречиво.

Теорема 1.Пусть φ1,..,φm,ψ – формулы АВ. Следующие условия эквивалентны:

1) ;

2)

3) {φ1,..,φm,¬ψ} – противоречивое множество формул;

4) – тождественно истинная формула;

5) φ1∧..∧φm∧¬ψ – тождественно ложная формула.

 

– Конец работы –

Эта тема принадлежит разделу:

ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ

Логика это наука о законах мышления Это одна из древнейших наук Основные законы логики были сформулированы еще древнегреческим мыслителем... Современная математическая логика определяется как раздел математики... Данное учебно практическое пособие соответствует учебной программе курса Математическая логика и теория алгоритмов...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ.

Эквивалентные формулы алгебры высказываний
Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы φ и ψ АВ называются

Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний
Если х — логическая переменная, δ {0,1}, то выражение   называется литерой. Литеры х и ¬х называются контрарными. Э

Определение формального исчисления
  Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия. 1. Имеется некоторое множество

Система аксиом и правил вывода
Используя понятие формального исчисления, определим исчисление высказываний (ИВ). Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются про

Теорема о дедукции в исчислении высказываний
Теорема 1(о дедукции). Пусть φ1,…,φm,φ,ψ – формулы ИВ. Тогда φ1,…,φm,φ⊢

Теорема о замене в исчисления высказываний
Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если φ⊢ψ и ψ⊢φ.

Свойства выводимых и эквивалентных формул исчисления высказываний
Утверждение 3.Пусть φ,ψ, χ – формулы ИВ. Тогда 1) ⊢φ→φ; 2) φ∧ψ⊢φ;

Высказываний
Теорема 3.Пусть φ, ψ, χ ‑ формулы ИВ. Тогда имеют место следующие эквивалентности: 1) φ∧ φ≡φ, φ∨

Высказываний
  Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тож

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

Формулы логики предикатов
Большинство определений этого параграфа будут индуктивными. Введем понятие атомарной формулы сигнатуры Σ: 1) если t1, t2, T(Σ), то

В алгебраической системе
  Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической с

Логическое следствие в логике предикатов
  Через обозначим кортеж переменных ; через ‑ . Пусть φ1(),…,φn(), ψ() – формулы сигнатуры . Формула ψ называетс

Эквивалентные формулы логики предикатов
Формулы φ и ψ сигнатуры называются эквивалентными (обозначается φ ≡ ψ), если φψ или ψ . Утвержден

Пренексная нормальная форма в логике предикатов
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной форм

Система аксиом и правил вывода
  Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ). Формулами ИПΣ

Предикатов
Утверждение 2.В ИПΣ выполнимы все эквивалентности ИВ из теоремы 3. Утверждение 3. Пусть φ

Исчисления предикатов
Теорема 4. Все доказуемые в ИПΣ формулы являются тождественно истинными. Доказательство проводим индукцией по длине вывода формулы. Очевид

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

Примитивно рекурсивные функции
  Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора. Оператор суперпозиции (подстановки) ставит в соот

Частично рекурсивные функции
  Оператор минимизации ставит в соответствие n+1-местной частичной функции n-местную частичную функцию так, что и или определены и не равны 0,

Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФ и СКНФ. 1. (x∧¬y)→(y∧z);

Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2. 1. ; 2. ; 3. ; 4. ; 5. ; 6.

Исчисление высказываний
  Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез. 1. ; 2. ; 3. ; 4. ;

Алгебраические системы.
Построить подсистему алгебраической системы , порожденную множеством (через обозначен булеан множества B, т.е. множество всех подмножеств множества B): 1. 2.

Формулы логики предикатов
  Выписать все подформулы данной формулы сигнатуры и определить свободные и связанные переменные формулы: 1. 2. 3. 4. 5.

В алгебраической системе
  Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда 1. х=1; 2. х=2n для некоторого натурального

Логическое следствие в логике предикатов
Пусть – формулы логики предикатов, и . . Доказать следующие соотношения. 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ;

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги