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)

0
votes
1answer
72 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.
2
votes
3answers
99 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
45 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 ...
5
votes
3answers
312 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
248 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
27 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
82 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 ...
3
votes
6answers
136 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
118 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
72 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
54 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
114 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
112 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 ...
1
vote
1answer
38 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
84 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
49 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
234 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 ...
4
votes
3answers
335 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
440 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
237 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
99 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
42 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
114 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 ...
3
votes
1answer
71 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 ...
2
votes
1answer
63 views

Question about implication with antecedent $P(x)$ of $x$ that is false for all values of $x$.

Suppose $x \in R^+$ and we want to prove the implication $x < 0 \Rightarrow P(x)$, where $P(x)$ is some statement of $x$. How should one tackle this situtation ? Normally one should prove the ...
1
vote
1answer
76 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 ...
6
votes
2answers
371 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
110 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
47 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
129 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
49 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
133 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
96 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
118 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
1k 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
125 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
37 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
39 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
2answers
61 views

Properties semantic equivalence proof - too many steps.

I would like to prove $$(p ⇒ q) ⇒ r ≡ (r \vee p) ∧ (q ⇒ r)$$ Have I used too many steps? It seems long. Mind you I do want to show each step individually so implication in two separate steps for ...
1
vote
1answer
68 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
49 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
226 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
38 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 ) ?
1
vote
2answers
60 views

Proof in logic that $P \Leftrightarrow Q$ is the same as $ (\lnot P \lor Q) \land (\lnot Q \lor P)$

How is it possible to prove that $P \Leftrightarrow Q$ is the same as $ (\lnot P \lor Q) \land (\lnot Q \lor P)$ using logic laws?
2
votes
2answers
53 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
35 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
42 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
42 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
421 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
43 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"?