The Foundations: Logic and Proofs (2)

 

Predicates

* 속성과 관계를 나타낸다. 명제와 달리, 주어와 술어를 구분하여 참 거짓 판단한다.

- x is greater than 3

    - x: variable      

    - is greater than 3: predicate P

    - P(x)                    :P(x)자체가 명제는 아니고 변수 x가 적절한 값으로 치환되면 결과적으로 명제가 된다.

 - Let Q(x,y) denote the statement “x=y+3”         

    - Q(1,2) is false but Q(3,0) is true                       하나 이상의 변수가 존재할 수 있다.

- n-place predicate (or n-ary predicate)     

    - P(x1 , x2 , … , xn )

-> 그 자체로는 바로 T, F 인지 구분 불가능. 

 

 

Quantifiers

˙Universal quantification: ∀x P(x)    모든 x 에 대하여

    -  A predicate is true for every element

    - If P(x) is x<2, is ∀x P(x) true for the domain of integers?

˙ Existential quantification: ∃x P(x)   어떤 x 에 대하여

    - A predicate is true for one or more elements

    - If P(x) is x<2, is ∃x P(x) true for the domain of integers?

˙ Precedence of Quantifiers

    - Quantifiers ∀ and ∃have higher precedence then all logical operators : 제일 높은 우선순위를 가짐.

    - ∀x P(x) ∨ Q(x) means (∀x P(x)) ∨ Q(x)

-> predicates에 quantifiers를 붙이면, T,F를 바로 판단 가능하다. 

     이때, universal(∀)또는 existential(∃)를 붙이냐 2가지 방법이 있다.

 

 

Logical Equivalences Involving Quantifiers

 

Nested Quantifiers

˙∀x ∃y(x+y=0)   ->  T

    - ∀x Q(x) where Q(x) is ∃y(x+y=0)

    - For every real number x, there is a real number y such that x+y=0

    - ∀x ∃y(x*y=0)   -> T  

˙∃y∀x(x+y=0)  -> F

    - ∃y Q(y) where Q(y) is ∀x(x+y=0) 

    - There is a real number y such that for every real number x, x+y=0

    - ∃y∀x(x*y=0)  -> T

˙Negating nested quantifiers

    -  ~∀x∃y(xy=1) ≡ ∃x ~∃y(xy=1) ≡ ∃x∀y~(xy=1) ≡ ∃x∀y(xy≠1)

 

 

Valid Arguments

˙ Argument

    - Sequence of propositions (p1 , p2 , …, pn ) 

    - Premises (p1 , p2 , …, pn-1 )

       :  All but the final proposition in the argument

˙ Conclusion (pn )

     - The final proposition

˙ The argument is valid if the truth of all its premises implies that the conclusion is true

     - Tautology: (p1 ∧ p2 ∧ … ∧ pn-1 ) -> pn   

        : 주어진 전제가 모두,동시에 true이면 결론은 무조건 true이다.

  If you have a password, then you can log onto the network    ---------------premises 

  You have a password                                                                                ---------------premises 

  Therefore, You can log onto the network                       --------------------------- conclusion

 

 

Rules of Inference

example 1.

˙ Hypotheses

    - Jasmine is skiing or it is not snowing

    - It is snowing or Bart is playing hockey 

˙ Conclusion

    - Jasmine is skiing or Bart is playing hockey

˙ p: it is snowing /q: Jasmine is skiing /r: Bart is playing hokey

 

     1. ~p∨q    Hypothesis  T

     2.   p∨r     Hypothesis  T

     3.   q∨r     Resolution (1) and (2)  T

 

example 2.

˙ Show that the hypotheses (p∧ q)∨r and r -> s imply the conclusion p∨s

 

    1. (p∧ q)∨r              Hypothesis

    2. (p∨r)∧ (p∨q)   Distributive law

    3.  p∨r                       Simplification

    4. r -> s                       Hypothesis

    5. ~r∨s

    6. p∨s                        Resolution (3) and (5)