Question

In: Computer Science

Give a formal proof for the following tautology by using the IP rule. (A →B) ^...

Give a formal proof for the following tautology by using the IP rule.

(A →B) ^ (B →C) →(A v B →C)

Expert Solution

Given (A B) (B C) (A V B C)

(¬A VB) (¬B VC) [¬(A V B) V C] { Law of Implies (PQ) = ¬PVQ }

[¬ {(¬A VB) (¬B VC) }] V [¬(A V B) V C] { Law of Implies (PQ) = ¬PVQ }

[ {¬(¬A VB) V ¬(¬B VC) }] V [(¬A ¬B) V C] {By De Morgan's law ¬ (PVQ) = ¬P ¬Q}

[ {(¬(¬A) ¬B) V (¬(¬B) ¬C) }] V [(¬A ¬B) V C] {By De Morgan's law ¬ (PVQ) = ¬P ¬Q}

[ {(A ¬B) V (B ¬C) }] V [(¬A ¬B) V C] {By De Morgan's law ¬ (¬ P) = P }

[ (A ¬B) V (B ¬C) ] V [C V (¬A ¬B)] { Commutative law P V Q = Q V P }

A [(¬B V B) (¬C V C)] V (¬A ¬B) {Associative law (A V B) V C = A V (B V C)}

A (¬A ¬B) V [(¬B V B) (¬C V C)] { Commutative law P Q = Q P }

A (¬A ¬B) V [(T) (T)] {We know that P V ¬ P = T}

(A ¬A) ¬B V [ (T) ] {We know that T T = T}

(F) ¬B V T {We know that P ¬P = F}

(F ¬B) V T {Associative law (A V B) V C = A V (B V C)}

(F) V T {We know that F ¬P = F}

T

Tautology

venereology answered 1 month ago

Give a formal proof for the following tautology by using the CP rule. A v B→(¬...

Give a formal proof for the following tautology by using the CP rule. A v B→(¬ B →(A ^ ¬ B))

Give a formal proof for the following tautology by using the CP rule. (A →(B →C))...

Give a formal proof for the following tautology by using the CP rule. (A →(B →C)) ^ B →(A →C)

Give a proof for the standard rule of differentiation, the Chain Rule. To do this, use...

Give a proof for the standard rule of differentiation, the Chain Rule. To do this, use the following information: 10.1.3 Suppose that the function f is differentiable at c, Then, if f′(c) > 0 and if c is an accumulation point of the set constructed by intersecting the domain of f with (c,∞), then there is a δ > 0 such that at each point xin the domain of f which lies in (c,c+δ) we have f(x) > f(c). If...

Let’s give a formal proof that RadixSort works and give a bound on its runtime. We...

Let’s give a formal proof that RadixSort works and give a bound on its runtime. We start with correctness: Lemma RadixSort will properly sort any n natural numbers. Prove this statement. You can use any strategy you want, but we recommend using induction on l (the number of digits that each value has).

For each of the following concepts: define it and give an example. a. rule b. rule...

For each of the following concepts: define it and give an example. a. rule b. rule control c. rule-governed behavior d. contingency control e. contingency-governed behavior (contingency-shaped behavior).

Write a formal proof to prove the following conjecture to be true or false. If the...

Write a formal proof to prove the following conjecture to be true or false. If the statement is true, write a formal proof of it. If the statement is false, provide a counterexample and a slightly modified statement that is true and write a formal proof of your new statement. Conjecture: Let w, x, y, and z be single-digit numbers. The 4-digit number wxyz* is divisible by 9 if and only if 9 divides the sum w + x +...

For the following IP A & B, do subnetting and give the first 5 Network IDs...

For the following IP A & B, do subnetting and give the first 5 Network IDs (Subnets) with first, last available IP addresses, and broadcast address. Class B: 150.5.0.0/16 A small company needs Cisco best practice: 500 Hosts per Network Class A: 10.0.0.0/8 The corporation needs: 1000 Hosts per Network

Is the following argument valid? If so, construct a formal proof (direct or indirect). If not,...

Is the following argument valid? If so, construct a formal proof (direct or indirect). If not, explain why not. If Alex gets a new job, then he will buy a guitar. If Alex wins the lottery, then he will buy a guitar. If Alex goes to Costa Rica, then either Alex got a new job or Alex won the lottery. Alex goes to Costa Rica. Therefore, Alex bought a guitar.

Proof that the NPV rule is equivalent to the rate of return rule if the investment...

Proof that the NPV rule is equivalent to the rate of return rule if the investment period is 1 Year.

Complete this formal proof of Ex(P(x)v~P(x)) from the empty set. NOTE: similar to the rule above...

Complete this formal proof of Ex(P(x)v~P(x)) from the empty set. NOTE: similar to the rule above when instantiating quantifiers, if you need a random name, always start at the beginning of the alphabet. That is, use a first; only use b if necessary; etc.