Q2.	(15 points) Is the statement (A ∧ B ∧ C) → D a valid argument. Justify your answer with a mathematical proof. Hint 1: a statement is valid if and only if its negation is a contradiction. Hint 2: try to simplify the body of the implication (i.e., the part A ∧ B ∧ C) before simplifying the entire formula. Hint 3: a quantified formula is a contradiction if and only if it is not possible to find a universe satisfying it.

(A ∧ B ∧ C) → D

= [∀x {H(x) → ¬R(x)}] ∧ [∀x {¬R(x) → ¬ G(x)}] ∧ [∀x {¬G(x) → ¬N(x)}] → D

since the universal quantifier (∀) distributes over conjunction:

= ∀x [{H(x) → ¬R(x)} ∧ {¬R(x) → ¬ G(x)} ∧ {¬G(x) → ¬N(x)}] → D

by using  the principle of transitivity of implication (in Hypothetical Syllogism) which tells us that (P→Q),(Q→R)⊢(P→R)

= ∀x [{H(x) → ¬ G(x)} ∧ {¬G(x) → ¬N(x)}] → D

= ∀x [H(x) → ¬N(x)] → D

put D in place

= { ∀x [H(x) → ¬N(x)] } → { ∀x [H(x) → ¬N(x)] }

by conditional laws

= ¬ { ∀x [H(x) → ¬N(x)] } ∨ { ∀x [H(x) → ¬N(x)] }


= ¬ { ∀x [¬H(x) ∨ ¬N(x)] } ∨ { ∀x [¬H(x) ∨ ¬N(x)] }

= {¬∀x [¬H(x) ∨ ¬N(x)] } ∨ { ∀x [¬H(x) ∨ ¬N(x)] }

by quantifier negation laws

= { ∃x ¬[¬H(x) ∨ ¬N(x)] } ∨ { ∀x [¬H(x) ∨ ¬N(x)] }

take the negation of this statement

negation = ¬ ( { ∃x ¬[¬H(x) ∨ ¬N(x)] } ∨ { ∀x [¬H(x) ∨ ¬N(x)] } )

by De Morgan’s law

negation = ¬{ ∃x ¬[¬H(x) ∨ ¬N(x)] }	 ∧ ¬{ ∀x [¬H(x) ∨ ¬N(x)] }

by quantifier negation laws

negation = {∀x [¬H(x) ∨ ¬N(x)] } ∧ { ∃x ¬[¬H(x) ∨ ¬N(x)] }

Let [¬H(x) ∨ ¬N(x)] = Z(x)

negation = {∀x Z(x) } ∧ { ∃x ¬Z(x) }

This is a contradiction since the statements “for all x, Z(x) is true” and “there exists an x for which Z(x) isn’t true contradict each other. When two contradicting statements are said to be true at the same time; there is a contradiction. There is no universe which x is an element of, that satisfies the negation of the original statement.

So the argument is valid since it’s negation is a contradiction.