# Tagged Questions

57 views

### How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $(p \equiv q) \equiv (q \equiv p)$. Given p and q ...
127 views

### Logic Confusing Problem

I Read one logic book, can my two conclusion are true? 1- Suppose for each valuation v, we have such n that can we say we have such n that 2- Suppose for each ...
92 views

### About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
53 views

### Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
99 views

### Which of $\varphi$ or $\lnot \varphi$ can be expressed by using only the $\rightarrow$ connective? [on hold]

if we have: $$\varphi = \lnot(p\land q\to r)$$ (original screenshot) a) we can write $\varphi$ in equivalence just by using $\to$ connective. b) we can write $\lnot\varphi$ in equivalence ...
56 views

### Prove A or (A and B) is equivalent to A [duplicate]

Prove $A \lor (A \land B) \Leftrightarrow A$ without using truth table. The proof may involve expanding $B$ into $B \land B$ or possibly $B \lor B$. I am stuck after playing with distributive law ...
40 views

30 views

### properties of semantic equivalence proof

I would like to prove using semantic equivalences that (p ⇒ q) ∧ (¬q ⇒ r) ≡ (r ⇒ p) ⇒ q but I keep getting stuck at the same point. Can someone please tell me ...
37 views

### double negation rule - properties of semantic equivalence

I know the rule for double negation is ¬(¬P) ≡ P However if I have: ¬(¬P V Q) does that give me ...
25 views

### semantic equivalence proof

Using properties of semantic equivalence I would like to prove: (p⇒r) ∧ (q⇒r) ≡ (p V q) ⇒ r I have wound up with the correct result however the steps it took to ...
88 views

### Law of excluded middle. Do we need it in proofs?

Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking: "lets start with some form of the law of the excluded middle (LEM) and ...
32 views

### Question on the Truth Table

How do you find out the number of rows that is needed for the truth table. For example, for A => B is a 4x2 table. What about if we want to make a table for, say, A => ( P => R ) ?
37 views

### Is P XOR (IF P THEN L) equal to NOT (P AND L)?

I would like to reduce this statement:$$P \veebar (P \implies B)$$ using only $\neg$, $\land$ I've found this solution but I don't know if I'm wrong: $$\neg(P \land B)$$ Because the book proposes ...
27 views

### Propositional Logic simplification

I was wondering if anyone could help me to understand how this is simplified: P v (P ^ Q) The answer is: 1) (P ^ T) v (P v Q) - apply Identity. 2) P ^ (T v Q) - apply Distributive. 3) (P ^ T) - ...
41 views

### $(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
47 views

### Compactness of Propositional Logic

I little confused on compactness of propositional logic. So propositional logic has the property of being compact, that is to say, given a set of formulas $\mathcal F$, then $\mathcal F$ is ...
62 views

### $P$: $((p \land q) \vee r)\implies (l \vee t)$… If $p$,$q$,and $l$ are all false and $r$ and $t$ are true determine if $P$ is true

$P$: $((p \land q) \vee r)\implies (l \vee t)$... If $p$,$q$,and $l$ are all false and $r$ and $t$ are true determine if $P$ is true. How would I show this just by logically writing out $p$ and ...
70 views

### Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
42 views

### Can there be a formula $\psi$ such that $(\psi \rightarrow (¬\psi))$ is a theorem of L?

Can there be a formula $\psi$ such that $(\psi \rightarrow (¬\psi))$ is a theorem of L? I would like to check my answer. I thought: No it cannot be a theorem of L. Because to be a theorem of L it ...
139 views

### Natural Deduction Tautology

I'm trying to prove the following tautologies: \begin{align} & ⊢ (A \to (B \to A)) \\ & ⊢ ((A \to B) \to A) \to A \end{align} For the first one, what I did was: $A$ assumption $B$ ...
Suppose I have an arbitrary formula $\Phi$ in propositional logic. Is there a way to convert $\Phi$ to a 2-CNF formula $\Psi$ such that $\Phi \equiv \Psi$? If not, why not?