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

Алгебра 11 класс Логика высказываний выполнимая формула алгебра высказываний логика истинность формулы математическая логика Новый

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

Определение:

Формула называется выполнимой, если существует хотя бы одна комбинация значений истинности переменных, при которой вся формула будет истинной.

Пример:

Рассмотрим формулу:

• p ∨ ¬q

Здесь p и q — это логические переменные. Формула состоит из операции "или" (∨) и операции "не" (¬).

Шаги для проверки выполнимости:

1. Выберем значения переменных p и q. Например, пусть p = истина, а q = ложь.
2. Подставим эти значения в формулу: истина ∨ не ложь = истина ∨ истина = истина.
3. Так как мы нашли хотя бы одно сочетание значений переменных, при котором формула истинна, то формула p ∨ ¬q является выполнимой.

Не выполнимая формула:

Для контраста, рассмотрим формулу:

• p ∧ ¬p

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

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