logo
практикум по мат

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

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

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

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

φ

ψ

χ

φ→ψ

ψ→χ

0

0

0

1

1

0

0

1

1

1

0

1

0

1

0

0

1

1

1

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

1

Из таблицы истинности видно, что когда все гипотезы принимают значение равное 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

0

1

1

1

0

0

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

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

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

  1. ;

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

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

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