Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

48 значения логической функции, представляемой формулой F , от значений переменных этой функции. Иначе говоря, если задана формула F(a 1 ,…,a n ) и задана ее интерпретация, то для выяснения истинности ее нужно вычислить как логическую функцию на наборе (  1 ,…,  n ) , где  i =1 , если a i =И и  i =0, если a i =Л . Если F(  1 ,…,  n )=1 , то F=И , если F(  1 ,…,  n )=0 , то F=Л . Поэтому вводить аксиомы и правила вывода мы не будем, а воспользуемся изученным аппаратом логических функций. Определение. Формула F называется общезначимой тогда и только тогда, когда она истинна при всех интерпретациях (необщезначима в противном случае). Определение Формула F называется противоречивой тогда и только тогда, когда она ложна при всех интерпретациях (в противном случае непротиворечива). F x x И 1 n  ) ..., ( – общезначима, непротиворечива F x x Л F y y И n 1 n 1   ) ,..., , ( ) ,..., ( – необщезначима, непротиворечива F x x Л n 1  ) ,..., ( – противоречива, необщезначима. Определение. Пусть даны формулы F 1 ,…,F n и формула G . G есть логическое следствие формул F 1 ,…,F n тогда и только тогда, когда для всякой интерпретации I , в которой F 1  …  F n истинна, G также истинна. ( F 1 ,…,F n называется посылками). Теорема 9.1. G есть логическое следствие F 1 ,…,F n тогда и только тогда, когда формула ((F 1  …  F n )  G) общезначима. Доказательство. Обозначим H= ((F 1  …  F n )  G) . Необходимость. Пусть G – логическое следствие F 1 ,…,F n . Если F i =И, i 1 n ,  , то G И  , следовательно Н=И . Если некоторое F i =Л в интерпретации I , то F 1  …  F n =Л в этой интерпретации, следовательно при G = И или G = Л обязательно H=И , т.е. H – общезначима.