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)

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
225 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
332 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
432 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
98 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
108 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
75 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
369 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
125 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
48 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
129 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
89 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
116 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
122 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
48 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
224 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
58 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
391 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"?
0
votes
2answers
66 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
164 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
72 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
78 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
44 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 ...
5
votes
3answers
583 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$ ...
1
vote
3answers
103 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
64 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?
2
votes
3answers
695 views

Propositional Logic Proof using I.P. or C.P or rules of inference

I'm attempting to solve a proof my professor asked. We are able to use any of the rules of inference, Indirect Proof or Conditional Proof. Every time I think am making progress I run into a brick ...
1
vote
1answer
59 views

Show that any consistent extension $L^*$ of L has a consistent extension ${{L^*}^*}$ which is complete.

If $L^*$ is a consistent extension of L and $\phi$ is a formula which is not a theorem of $L^*$ , then the extension of $L^*$ obtained by including $(¬\phi)$ as an extra axiom is consistent. Show ...
1
vote
1answer
78 views

Mathematical Logic Past Paper Question: n is a positive integer, $X_n$ = ${(x_1,.,x_n) : x_i ∈ {T,F}}$ is the set of n- tuples from {T,F}.

Suppose $n$ is a positive integer and $X_n = \{(x_1,\ldots ,x_n) \colon x_i ∈ \{T,F\}\}$ is the set of $n$- tuples from $\{T,F\}$. Suppose $f\colon X_n \to \{T,F\}$ is a function and $f(x) = T$ for ...
2
votes
4answers
87 views

Hilbert System with propositional logic $p \rightarrow q,\neg q \vdash \neg p$

This is my set of axiom $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A ...
0
votes
1answer
59 views

Hilbert proof systems with hypothesis

This is my set of axioms: $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A ...
4
votes
4answers
126 views

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L.

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L. So every axiom is a theorem of L so I thought there would be some way to ...
1
vote
0answers
29 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...