Четверг, 28.03.2024, 12:40
Мой сайт
Приветствую Вас Гость | RSS
Меню сайта
Категории раздела
Основы логики [11]
История логики [8]
Логика мышления [4]
Практическая логика [5]
Законы логики [13]
Наш опрос
Оцените мой сайт
Всего ответов: 805
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Логика » Практическая логика

Практическая логика. Полные системы логических операций

Практическая логика.

Полные системы логических операций

Возможность вывести любую тавтологию в чрезвычайно простом исчислении Гильберта всего с двумя операциями ¬ и Ъ наводит на вопрос, достаточно ли широко наше понятие пропозициональной формулы, чтобы охватывать все способы образования высказываний? Нет ли каких-нибудь новых логических операций, которые нельзя было бы выразить через ¬ и Ъ, и использование которых сильно расширило бы возможности нашего формального логического языка? Покажем, что таких операций нет.

Каждая мыслимая логическая операция над n высказываниями определяется соответствующей функцией f(A1,А2,...,An) от n логических переменных, принимающей значения И или Л для каждого набора значений своих аргументов. Такая функция называется логической и задаётся таблицей

А1А2...Аnf(А1, А2, ..., Аn)
Все комбинации логических значений
для n переменных.

Всего таких комбинаций 2n,
столько же и строк в таблице
(не считая строки с формулами).

 

Значения функции

Поскольку столбец значений f(А1, А2, ..., Аn) содержит 2n букв И или Л, всего возможных логических функций от n переменных будет . Так, число 2-местных логических функций (n = 2) равно 16, а мы использовали только 4. 3-местных функций уже 256. Ответ на наш вопрос даёт следующая теорема.

Теорема (об определении логических функций).

Любая n-местная (n>0) логическая функция определяется некоторой пропозициональной формулой, содержащей только операции  ¬и Ъ.

Доказательство.  Возможны два случая.
1) Функция f(А1, А2, ..., Аn) тожественно ложна, т.е. в правом столбце определяющей её таблицы стоят только значения Л. Такая такая функция определяется тождественно ложной формулой

¬(А1Ъ¬А1ЪА2Ъ¬А2Ъ ... ЪАnЪ¬Аn).

2) Функция f(А1, А2, ..., Аn) принимает значения И при некоторых или при всех наборах значений аргументов. Рассмотрим строки её таблицы, в которых значение f равно И. Для каждой такой строки с номером i определим формулу ji как конъюнкцию переменных или их отрицаний: если Аj имеет значение И, то в ji включается Аj, а если Аj имеет значение Л, то в ji включается ¬Аj. Например, для функции с таблицей

номер
строки
А1А2А3А4f(А1, А2, А3, А4)
      
iИЛЛИИ
      

формула ji будет иметь вид А1Щ ¬А2Щ ¬А3ЩА4. Так построенная формула ji будет истинна только при тех значениях переменных, которые они принимают в i-той строке таблицы. Следовательно, дизъюнкция j всех построенных формул ji (напомним, что i - это номер строки, в которой функция f имеет значение И) истинна только в тех строках, в которых истинна и f. Остаётся лишь заменить в формуле j конъюнкцию на дизъюнкцию по закону (АЩВ)«¬(¬АЪ¬В).

Пример. Для операции "исключающая дизъюнкция" A Е B построение определяющей формулы, описанное в доказательстве теоремы, имеет вид

номер
строки
ABAЕBji
1ИИЛнет
2ИЛИАЩ¬В
3ЛИИ¬АЩВ
4ЛЛЛнет

Эта таблица даёт определяющую формулу j как дизъюнкцию j2Ъj3, т.е. АЩ¬ВЪ¬АЩВ. Заменяя Щ на Ъ, получим j в виде ¬(¬АЪ¬¬В)Ъ¬(¬¬АЪ¬В), или после упрощения по закону двойного отрицания

 ¬(¬АЪВ)Ъ¬(АЪ¬В).

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

Следствие. Любой набор логических функций, содержащий операции ¬ и Ъ или ¬ и Щ, образует полную систему логических операций. В частности, системы операций {¬, Ъ}, {¬, Щ} и {¬, Ъ, Щ} являются полными.

Существуют полные наборы операций, содержащие всего по одной операции. Это системы {Ї} и {­}, где операции Ї и ­ определяются формулами:

АЇВ« ¬(АЪВ)    (операция Пирса)
А­В« ¬(АЩВ)    (операция Шеффера).

Это следует из тавтологичности формул 

¬А«АЇААЪВ« ¬(АЇВ), 
¬А«А­ААЩВ« ¬(А­В), 

а также из полноты систем операций {¬, Ъ}и {¬, Щ}.

 



Источник: http://public.uic.rsu.ru/~skritski/math-inf/Sect01.htm
Категория: Практическая логика | Добавил: sova (29.05.2009)
Просмотров: 3753 | Теги: логика | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Copyright MyCorp © 2024Бесплатный конструктор сайтов - uCoz