1
vote
1answer
34 views

Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...
1
vote
1answer
48 views

Prove or refute: $A_1,\ldots,A_n\vdash_{CPL} B \iff (A_1 \wedge \ldots \wedge A_n)\vdash_{CPL} B$

Need to prove or refute: $A_1, \ldots, A_n \vdash_{\rm CPL} B \iff A_1 \land\dots\land A_n \vdash_{\rm CPL} B$ Since we have $\iff$ operator, we have to deal with to directions. Let's begin from ...
2
votes
2answers
66 views

Prove or refute contingent: If A implies B is contingent, then B is too

The question is: If $A, A \to B$ are contingent, then so is $B$ $A, A \to B$ (implies) is a contingent, but how exactly to show «so is $B$»? If I'm using a truth table, how should I show that ...
3
votes
2answers
40 views

Prove/refute: Every tautology is contingent

I'm asking to prove/refute the following statement: Every tautology is contingent. According to definition of contingent: A statement that is neither self-contradictory nor tautological is ...
0
votes
1answer
56 views

Rooted Trees & Induction

So I am a little stumbled upon this question: A full binary tree is a rooted tree where each leaf is at the same distance from the root and each internal node has exactly two children. Inductively, a ...
2
votes
2answers
107 views

Rules of inference proofs

I have the following: Premise: {$p \lor q, q\rightarrow r,p \land s \rightarrow t, \lnot r, \lnot q \rightarrow u \land s$}, conclusion: $t$ I'm having a real hard understanding how to prove the ...
1
vote
2answers
101 views

Tautological implication

Determine whether or not $((P\land Q)\implies R)$ tautologically implies $((P\implies R)\lor (Q\implies R))$ How do I determine that $((P\land Q)\implies R)$ tautologically implies $((P\implies ...
0
votes
1answer
105 views

Constructing Proof Trees for Natural Deduction

I'm in the process of learning the process of writing so-called proof trees for $\textit{Natural Deduction}$. One question that I still grapple with is the actual process According to Van Dalen ...
0
votes
1answer
506 views

Induction proof for the lengths of well-formed formulas (wffs)

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible. The wffs in question are those associated with sentential/propositional logic. So, ...
3
votes
4answers
670 views

How to prove Disjunction Elimination rule of inference

I've looked at the tableau proofs of many rules of inference (double-negation, disjunction is commutative, modus tollendo ponens, and others), and they all seem to use the so-called "or-elimination" ...
0
votes
1answer
34 views

Definition by Recursion and a Question about Induction

I have some questions to ask. Suppose I want to define some sequence of propositional formulas $\{\varphi_{j}\}_{j\in\mathbb{N}}$. First, I define it this way. Fix an enumeration ...
2
votes
1answer
93 views

What is the difference between $Γ⊭Φ$ and $Γ⊭¬Φ$?

Did I understand this correctly? $Γ⊨Φ$ ($Φ$ is considered true) $Γ⊨¬Φ$ ($Φ$ is considered false) $Γ⊭Φ$ ($Φ$ is considered neither true nor false) $Γ⊭¬Φ$ ??? Please help me understand. How can ...
1
vote
1answer
102 views

Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$ is a tautology

Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$ Please could someone give me some feed back on this proof? Does it look correct? = $\lnot ((p\lor q)\land(p\lor(\lnot q)))\lor p$ = $ ...
0
votes
1answer
78 views

Verify these logical equivalences by writing an equivalence proof?

I have two parts to this question - I need to verify each of the following by writing an equivalence proof: $p \to (q \land r) \equiv (p \to q) \land (p \to r)$ $(p \to q) \land (p \lor q) \equiv q$ ...
1
vote
1answer
338 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
1answer
38 views

How can I progress this derivation?

I'm learning propositional calculus in a discrete mathematics course. I'm trying to kick the habit of using axioms like equations and now I'm a little stuck and could use a nudge. Using a compact ...
2
votes
1answer
90 views

Does this proof using Novikov axiomatic propositional logic hold?

This question seems absolutely elementary but I'm having a hard time completing the proof, in fact I may have taken a bit of a left turn on it or I may be improperly applying axioms all together. ...
1
vote
2answers
261 views

Predicate Logic Argument Validity

My question is whether or not the following is a validly structured argument: (P→T)→Q Q → ¬Q ∴ P I'm getting hung up on the Q→¬Q part by itself as a premise, it doesn't seem like that is ...
2
votes
3answers
233 views

Logical propositions, which one is true and how to write a short proof?

I am studying for an entrance exam. Now I am stuck on this question: Suppose that P, Q are propositions such that "P or Q" is true. For each proposition (1), (2) and (3) which of the following ...