Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

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
67 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
87 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
94 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
61 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
41 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
93 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 ...
1
vote
1answer
41 views

The logical consequence of an empty set of premises.

I am studying propositional logic by self-study, using a dutch book. I hope I am translating the terms to the correct English term. If my words are confusing, please please just let me know instead of ...
0
votes
1answer
25 views

How does the propositional logic of the following IFF proof (DAGs and topological ordering) work?

I was reading the following proof and am having trouble following the propositional logic underpinning the proof: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/DAG.html To ...
0
votes
0answers
67 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
35 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
58 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
105 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
259 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
221 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
1answer
89 views

How make equivalent transformations?

Please, help me make equivalent transformations with this formula (A∨C→B)(A→C)(¬B→¬A∧C)(¬A→(C→B))(B→¬C→¬A). Thanks.
2
votes
1answer
30 views

Write $(p\land q)\leftrightarrow (\neg p\lor \neg q)$ in CNF

I need to convert the below for a homework question and I am not entirely sure if it's correct. The last part is that I am not sure how to use the distributive laws in this scenario. Any guidance ...
0
votes
2answers
54 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
66 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
55 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
283 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
2answers
100 views

Solving a contradiction in premises

I've got a set of premises: $m \rightarrow j, a \rightarrow j, \neg m \rightarrow a, a \rightarrow \neg j$ Clearly, $a \rightarrow \neg j$ Contradicts $a \rightarrow j$ I'm asked to proof that out ...
0
votes
1answer
40 views

Help with axiom in propositional logic

I have an example in a propositional logic course I'm taking and I can't figure out how a certain axiom is/why it is applied in a certain step. This link: http://www.logicinaction.org/docs/ch2.pdf ...
0
votes
1answer
69 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
3answers
39 views

Propositional logic De-morgans theorem question

the theorem states that $(A\wedge B) = \neg (\neg A\vee \neg B)$, where $A$ and $B$ are propositional formulas. Can't I turn $\neg (\neg A\vee \neg B)$ to $(\neg \neg A\vee \neg \neg B)$ then cancel ...
1
vote
2answers
84 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
48 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
47 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
941 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
48 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
34 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
38 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
27 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
92 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
33 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
39 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
31 views

It is false that if p then q.

I'm doing some homework in which I'm converting textual descriptions of logic statements to their respective symbolic representation. If one reads ...
1
vote
2answers
38 views

How is this simplification done?

The models of the formula $p \rightarrow \neg(q \rightarrow r)$ are $V_{2}, V_{5}, V_{6}, V_{7}, V_{8}$. In disjunctive normal form this would be: $(p \wedge q \wedge \neg r) \vee (\neg p \wedge q ...
0
votes
1answer
32 views

Quantifier-free first-order formula equal to propositional formula

I just came across the term quantifier-free first-order formula, I first thought that might be similar to a propositional formula, but then after a closer evaluation I realized there are more concepts ...
1
vote
1answer
30 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 ...
3
votes
1answer
55 views

Natural Deductions of Propositional Logic and Predicate Logic

I'm trying to prove the following: ¬(A --> B) ⊢ ¬(¬A v B) ¬(¬A v B) ⊢ (A ^ ¬B) ∀x∀y(P(x, y) --> ¬P(x, y)) ⊢ ∀x¬P(x, x) For the first two, I feel like the first step is try assume the ...
0
votes
2answers
63 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
72 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
152 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
63 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
34 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?