1
vote
2answers
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 ...
0
votes
2answers
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 ...
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
4answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
40 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
3answers
84 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
1
vote
1answer
31 views

From statement to logic

I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian): Martha is not a singer, and she doesn't play violin or flute, but not ...
4
votes
2answers
163 views

Simplifying a categorical proof of constructive dilemma

In axiomatic propositional calculus the following axiom schema captures constructive dilemma: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$ \begin{equation} (a \lif c) \lif ((b \lif c) ...
1
vote
1answer
31 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
2
votes
1answer
21 views

Proposition Question

I am trying to translate this into propositional symbols but (for me) it's so complicated. Can someone help me figure this out. "If it rains then I will carry a sharp object and I will start laughing ...
0
votes
2answers
62 views

How to express $\lnot (a < b < 0)$ or the contrapositive of this statement?

I can't seem to get the negation, $\lnot (a < b < 0)$, right. I thought I could break it into 3 parts: a < b, a < 0, b < 0, but that leaves me with a > b or a > 0 or b > 0 (greater or ...
2
votes
5answers
84 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
3
votes
2answers
92 views

Why is removing the negation worse than adding it?

Natural Deduction Rule (¬I): Natural Deduction Rule (RAA): My book [Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007)]presents these two rules and then adds: The use of (RAA) can ...
2
votes
1answer
55 views

A simpler derivation of ($\phi \lor (\neg \phi)$)

In Chiswell&Hodges [Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007)] they use this derivation to prove ($\phi \lor (\neg \phi)$): A page earlier they used a simpler derivation that ...
1
vote
1answer
39 views

Is there a proof of this statement about deductions?

Is there a proof of the following statement: you cannot prove with natural deduction theorems that are unprovable in a Hilbert-style proof system? The logic in discussion is either propositional logic ...
1
vote
1answer
46 views

Prove that the disjunctions of all conjucts is a disjunctive normal form

Question: I am attempting the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1408. Prove that if $\mathbf{A}$ is a wff ...
0
votes
0answers
57 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
4
votes
1answer
33 views

Discrete 101: Validity of proof: Finding that p→q ∨ ¬r, q→p∧r, therefore p→r is invalid.

I'm sorry to bother with what apparently is a very easy Basic Logic question, but in my class'es notes there's an example that the professor probably explained in class: ...
2
votes
1answer
56 views

Fitch-Style First Order Logic

I have been stuck on this proof for a while. Here's where I'm at: Goal $(\neg B \to \neg A) \leftrightarrow (A \to B)$ l 1. $A \to B$ ll 2. $\neg B$ lll 3. $A$ lll 4. $B$ Elim 1,3 ...
3
votes
3answers
101 views

Fitch-Style Proof

Hi I'm having trouble solving a Fitch Style Proof and I was hoping someone would be able to help me. Premises: $A \land (B \lor C)$ $B \to D$ $C \to E$ Goal: $\neg E \to D$ Thank You
4
votes
3answers
245 views

P entails Q implies P

I have been looking at the following: P entails Q implies P And developed the proof as follows: ...
3
votes
4answers
215 views

How to prove this type of equivalence?

Show that from: $P \ \rlap\Leftarrow\Rightarrow Q$. It follows that: $(P \Rightarrow R)\, \rlap\Leftarrow\Rightarrow (Q \Rightarrow R)$ I don't understand where the $R$ suddenly came from? I try to ...
0
votes
2answers
47 views

Using DeMorgan’s rule, state the negation of the statement

Using DeMorgan’s rule, state the negation of the statement: “The car is out of gas or the fuel line is plugged.” Let C stand for “The car is out of gas” and let F stand for “the fuel line is ...
2
votes
1answer
65 views

Understanding the connective '$\vee$'

I have just started studying mathematical reasoning and have come through one simple foolish problem. I have learn that if '$\vee$' is used as connective and if any one component statement is true ...
1
vote
1answer
54 views

Using the compactness theorem

I am working through problems which ask you to apply the compactness theorem (from propositional logic) to problems. How would you go about solving this one? Let $\mathbf{L}$ be an arbitrary ...
5
votes
2answers
273 views

**Competition** Shortest Proof of Lukasiewicz's 13 Letter Axiom for Implicational Calculus from Tarski-Bernays

Spurred on by Willemien's competition, I thought I'd post my own. In 1948 a paper by Jan Lukasiewicz got published that established a 13 letter formula as (one of?) the shortest single axioms, under ...
0
votes
1answer
63 views

Conditional Introduction Rule

In the derivation (the image below) the author shows that given the premise $\neg S \land \neg J$, the conclusion is $S \implies J$. All these deductive maneuver for concluding implications I find ...
1
vote
2answers
81 views

Negation rules in natural deductive systems

This question concerns the block of text at the bottom, which is from Teller's Logic Primer, Chapter 5 (page 72). (I must mention that there is a rule called Negation Introduction. It says that when ...
3
votes
1answer
47 views

Translating sentences with causality into logical propositions

The author says that the sentence in a) is impossible to translate into the language of logic, but it is possible for the sentence in c). And I can not understand why, the second sentence is about the ...
0
votes
1answer
36 views

exclusive or logic truth table - not understanding why it is the way it is

In terms of logic and truth tables why is it that the truth table for exclusive or is as follows: Consider $P$ and $Q$. Let $P + Q$ denote exclusive or. Then if $P$ and $Q$ are both true or are both ...
10
votes
5answers
915 views

What is a false premise?

I don't understand what a sound argument is. And what does it mean for a premise to be false? Why does case 3 (A is false, B is true) not apply in the real world? Here the author says that the first ...
1
vote
1answer
40 views

Translating natural language to propositional logic

I have been given the following assignment: Charles is rich or clever. If Charles was clever, he'd have a job. But, Charles doesn't have a job, so he must be rich. The translation I gave (verified ...
0
votes
1answer
32 views

Applying Commutivity Law to a Tautology $P\lor \neg (P \land Q) $

How do I apply Commutivity law to a tautology: $P\lor \neg(P \land Q)$? I understand the it is $A\lor B = B\lor A$, but how can this apply to the above tautology? Do I assume $P$ as $A$, and $\neg ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ) ?
2
votes
2answers
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 ...
1
vote
1answer
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) - ...
1
vote
1answer
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"?
0
votes
2answers
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 ...
0
votes
2answers
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 ...
2
votes
0answers
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: ...
3
votes
2answers
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 ...
4
votes
3answers
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$ ...
0
votes
2answers
50 views

Can There Get Found Single Axioms for Some Subsystems of Propositional Calculus?

I use Polish notation. All systems have detachment and uniform substitution as the only primitive rules of the system. A user named John told me in an answer "On the question of a single axiom, the ...
0
votes
1answer
33 views

Can an arbitrary formula in propositional logic be converted to 2CNF, preserving equivalence?

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?