Proof by modus tollens To prove p ⇒ q we prove [( ∼ q ) ∧ ( p ⇒ q )] ⇒ ( ∼ p ) instead. Example: We know, that if a right triangle has sides of lengths a, b, c , which c is the largest, then a 2 + b 2 = c 2 ( p ⇒ q ). Therefore, if we prove that for any triangle with sides of lengths x, y, z ,...
Properties of generalized union and intersection. Property 1: For every ( A t ) t 2 T : 1) ∀ t ∈ T A t ⊂ S t 2 T A t ∧ T t 2 T A t ⊂ A t ; 2) ∀ t ∈ T A t ⊂ A ⇒ S t 2 T A t ⊂ A ; 3) ∀ t ∈ T A ⊂ A t ⇒ A ⊂ T t 2 T A t ; 4) A ∪ ( S t 2 T A t ) = S t 2 T ( A ∪ A t ); A ∩ ( S t 2 T A t ) = S t 2 T ( A ∩ ...
Properties of quantifiers The commutative properties of quantifiers ∀ x ∀ y p ( x, y ) ⇐⇒ ∀ y ∀ x p ( x, y ) ; ∃ x ∃ y p ( x, y ) ⇐⇒ ∃ y ∃ x p ( x, y ) . But the order of universal and existential quantifiers cannot be changed. ∀ x ∃ y p ( x, y ) ⇐ = ∃ y ∀ x p ( x, y ) .
Properties of union intersection and complement. Property 1 (Properties of ∅ and U (universal set)): A ∪ ∅ = A ; A ∪ U = U ; A ∩ U = A ; A ∩ ∅ = ∅ . Property 2 (The idempotent properties): A ∪ A = A ; A ∩ A = A. Property 3 (The commutative properties): A ∪ B = B ∪ A ; A ∩ B = B ∩ A. Property 4 (The...
Quantifiers Quantifiers are symbols used instead of words ”for every” and ” there exists”. ∀ - ”for every”, ”for all”, ”for each” - universal quantifier, big quantifier . Universal quantifier is a generalization of the conjunction: ∀ x p ( x ) means that p ( x 1 ) ∧ p ( x 2 ) ∧ ... ∧ p ( x n ) is t...
Tautologies (5) [ ∼ ( p ⇒ q )] ⇔ [ p ∧ ( ∼ q )] (law of the negation of implication, also used in the form:) (5') ( p ⇒ q ) ⇔ [( ∼ p ) ∨ q ] (6) ( p ⇔ q ) ⇔ [( p ⇒ q ) ∧ ( q ⇒ p )] (connection between equivalence and implication) (7) [( p ⇒ r ) ∧ ( r ⇒ q )] ⇒ ( p ⇒ q ) (law of transitivity of im...
Tautology and contradiction A compound statement that is always true, regardless of what truth values are assigned to its statement variables, is called a tautology or a logic law . Such a statement is logically true . A compound statement that is always false, regardless of what truth values are a...
The truth function Let S be a compound statement. We can define a function f S , called the truth function of S , in the following way 1 If S contains the n distinct statement variables p 1 , p 2 , ..., p n , and no others, then the truth function f S is a function of n variables x 1 , x 2 , ..., x...
Truth table We can use the above rules to find the truth tables of more complex compound statements. Let's consider ( p ∧ ∼ q ) ⇐⇒ ( ∼ p = ⇒ q ) ( ⋆ ) p q ∼ p ∼ q p ∧ ∼ q ∼ p = ⇒ q ( ⋆ ) 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 1 p, q - statement variables The number of rows in the tru...
COMPLEMENT OF A SET Let U be a universal set, it means a set including all the sets under discussion (some space). The complement of A in U is the set of all elements of U, that are not in A (difference of U and A): A = U \ A = {a : a ∈ U ∧ a /∈ A}.
