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)

1
vote
3answers
45 views

When I can reverse the logical operators?

I heard say that is logically equivalent to say it: $$\neg (p \vee q) = p \land q$$ So every time you have a negation operator in front can make a "distributive" altering the operator from within? ...
0
votes
1answer
34 views

Logical implications in classic logic

I have the following problem: If Joseph is playing piano or Joaquim is playing guitar, then John is not sleeping. I perfectly understood the situation but didn't understand the second row of ...
1
vote
0answers
30 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
2
votes
1answer
52 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
1
vote
1answer
44 views

Find the murderer by using truth table for formal logic (formal disjunction or formal implication)

I'm studying formal logic and i was wondering if you can check whether I've solved this task correctly. TASK. Two people are arrested as suspects for a murder case, Stan and Peter. Four witnesses ...
1
vote
2answers
69 views

is this proposition (inference) valid?

Is this inference valid or invalid? Why and how to prove this kind of question? $$p \rightarrow q, \neg q \rightarrow r , r \vDash p $$ Would a single truth table be enough for all types?
0
votes
1answer
31 views

Disjunction Elimination Proof

P∨(Q∨R) ⊢ Q∨(P∨R) Proof: 1.) P∨(Q∨R) Assumption 2.) P Assumption 3.) P∨R 2.) Disjunction Introduction 4.) Q∨(P∨R) 3.) Disjunction Introduction 5.) Q∨R Assumption 6.) Q ...
8
votes
4answers
711 views

Is the following a valid mathematical statement?

For all $f:\mathbb N\to\{1,2,3,\ldots,100\}$, If $f$ is a one to one correspondence, Then $f^{-1}(2)=3$ It seems as though this should not be a valid statement, since the implication fails to ...
11
votes
1answer
183 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
2
votes
2answers
115 views

Difference between Logical Axioms and Rules of Inference

What's the difference between Logical Axioms and Rules of Inference? In my understanding, both are ordered pairs of formulas which are used to reach a conclusion through syllogisms. My questions ...
6
votes
3answers
75 views

Difference between Gentzen and Hilbert Calculi

What is the difference between Gentzen and Hilbert Calculi? From my understanding from the reading of Rautenberg's Concise Introduction to Mathematical Logic, Gentzen calculus is based on sequents ...
0
votes
2answers
20 views

Substitutions as mappings from the set of Propositional Variables to the set of Formulas

Rautenberg defines substitutions in propositional calculus as follows: " A (propositional) substitution is a mapping σ : PV →F that is extended in a natural way to a mapping σ : F → F " PV: set of ...
2
votes
1answer
50 views

Are there any consistency proofs for propositional or first-order logic?

Take for example the Hilbert-style axiomatizations of the propositional and first-order calculus. Since a crucial point when operating with a proof system is that no contradictions must be found in ...
0
votes
1answer
14 views

Epress $\exists! x P(x)$using universal quantifications, existential quantifications and logical operators

Epress the quantification $\exists! x P(x)$, using universal quantifications, existential quantifications and logical operators. Does anyone have an idea?
3
votes
1answer
57 views

No truth function that is expressed by a formula that uses only implication and equivalence connectives

I proved the following statement by induction: Let $A$ be a propositional formula which uses only the connectives $→$ and $↔$. Prove (by induction on the complexity of $A$) that if every ...
-1
votes
1answer
65 views

Difference between DNF and CNF

I'm stuck on a particular question, about Propositional Logic. Let $A$ be the propositional formula $((\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r))$. Find a propositional ...
0
votes
2answers
77 views

Prove propositional logic by resolution.

Prove $$[(p→q) \wedge (qr→s)]\to [pr→s],$$ which is the same as $$[(\lnot p\lor q) \wedge (\lnot (qr) \lor s)]\to [\lnot (pr) \lor s]$$ I believe it can just be done with algebra rules, but I got ...
2
votes
1answer
62 views

Lindenbaum-Theorem only concerning sentential logic provable in ZF?

Is the Lindenbaum-Theorem of sentential logic (= propositional logic) provable in ZF (i. e. without the axiom of choice)? Lindenbaum's theorem of sentential logic states that every set $\Sigma$ of ...
1
vote
1answer
66 views

Proving by induction on the length of a propositional formula?

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number ...
1
vote
1answer
22 views

Writing in disjunctive normal form using logical laws

I'm having trouble converting the below formula to disjunctive normal form using logical laws. I found the DNF using truth tables but I am having issues using just logical laws. Here is the formula: ...
1
vote
1answer
46 views

$(Ǝx)H(x) \dashv \vdash (Ǝy)H(y)$?

I can prove the statement using the natural deduction, but I keep getting confused about this sequent, so it would be very thankful if someone can help me to understand this concept of predicate ...
0
votes
0answers
37 views

Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true: $((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$ Where the $\oplus$ operator is defined as: ...
1
vote
3answers
35 views

Showing tautology without a truth table.

Show that the conditional statement is a tautology without using a truth table. $a)$ $(p \wedge q) \rightarrow p$ My suggestion would be getting rid of the implication first, so $(p \wedge q) ...
1
vote
2answers
28 views

Natural deduction proof for : p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c

I am trying to prove the following statement but I am getting stuck at the 6th line and I'm unsure how to continue. p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c p → ( c ∨ b) (premise) b → s (premise) ...
0
votes
3answers
58 views

Proving $(p \oplus q) \oplus r=p \oplus (q \oplus r)$

I was assigned to prove the associative law on xor. $(p \oplus q) \oplus r=p \oplus (q \oplus r)$ I'm sure $(p\oplus q)=(p∧¬q)∨(¬p∧q)$ But I got stuck on $(p \oplus q) \oplus ...
2
votes
1answer
54 views

Creating a proposition from a truth table using only ~ ⋀ and v

I have to find a simple expression for the third column in the truth table using only the logical connectives I've mention above. There are two questions that are involved here. Problem 1: Truth ...
1
vote
0answers
34 views

Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and ...
1
vote
1answer
26 views

Can you give a simple CDCL example?

I am trying to understand how Conflict-Driven Clause Learning works. After reading through the lecture slides, wikipedia article and some additional slides I found online I realized that I still can't ...
1
vote
2answers
28 views

Can I use De Morgan's law in the third step as shown below to solve this problem?

$(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(\neg p \vee q) \wedge (p \vee q)$ $\equiv \neg(\neg (\neg p \vee q) \vee \neg(p ...
3
votes
1answer
47 views

Simplifying propositional logic

Hi I asked a question a few hours ago which has been solved but I got stuck on another exercise so I thought I'd reach out for some help. I have the premise: $((A \to B) \land (\lnot A \to C))$ ...
1
vote
1answer
35 views

How can i prove $p\to (q \vee r) \equiv (p \wedge \sim q) \to r$?

please Help me in this question i have tried to solve it like this: $$p \to (q \vee r) \equiv (p \wedge \sim q)\to r$$ $$p \vee \sim (q \vee r) \equiv \sim(p \wedge q)\vee r$$ $$p \vee \sim q \wedge ...
2
votes
2answers
68 views

Help with natural deduction (Propositional logic)

I'm trying to get to $(\neg A \to C)$ from the following formula: $$(A \wedge B) \vee (\neg A \wedge C)$$ I have attempted the following: $$((A \wedge B) \vee \neg A) \wedge ((A \wedge B) \vee C ...
0
votes
3answers
58 views

Verifying logic without drawing truth tables

Want to know is there a way to solve these sort of problems without drawing truth tables? I found that it's kinda time consuming drawing truth table for each question. Help pls. Check the images ...
3
votes
2answers
117 views

Why is the implication “If pigs could fly, I'd be king” a true implication? [duplicate]

Let $P$ = "Pigs can fly" and $Q$ = "I'm king". Apparently, there's a rule stating that $P \implies Q$ is true, if $P$ is false. In this example, $P$ is indeed false, because pigs cannot fly. But how ...
0
votes
1answer
46 views

What does “resolve away” exactly mean in propositional logic?

I have never had logic classes so I always struggle with the assignments that concern this interesting field. I was reading the slides about resolution theorem proving and there was a step-by-step ...
1
vote
0answers
71 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
2
votes
1answer
31 views

Are the following logical statements equal? Solution verification

We were requested to rewrite the following statement: \begin{equation*} ((\phi \rightarrow(\psi \lor \lnot X)) \land (\phi \rightarrow (\psi \land X))) \end{equation*} using $\exists, \land, \lnot $ ...
1
vote
3answers
92 views

How is “p implies q” same as “q unless not p”?

I want to know how is "p implies q" same as "q unless not p"? ie how is "$p\Rightarrow q$" same as "$q$ unless $\neg p$" ?
-1
votes
3answers
56 views

Prove that the set of sentences $\{A \land (B \lor C), (\lnot C \lor H) \land (H \rightarrow \lnot H), \lnot B\}$ is inconsistent

Prove that the set of sentences $\left\{A \land (B \lor C), (¬C \lor H) \land (H \to \lnot H), \lnot B\right\}$ is inconsistent. I'm confused because it doesn't look like any of the forms I've ...
2
votes
2answers
47 views

A Natural-Deduction proof of $ \{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $.

I would like to prove $\{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $. My work until now is as follows: $$ \begin{array}{l|ll} 1 & \neg N ...
0
votes
1answer
46 views

Prove that the following argument is valid

I'm asked to show the following arguments are valid: P1) $[E \lor (L \lor M)] \land (E \leftrightarrow F)$ P2) $L \rightarrow D$ P3) $D \rightarrow \neg L$ C) $E \lor M$ Our work (so far): P2) ...
1
vote
1answer
49 views

Natural deduction proof: {A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A

$ 1- {A → B, B → (C \land D), ¬C \vee ¬D} ⊢ ¬A$ Our work (so far): $1- A → B$ $2- B → (C \land D)$ $3- ¬¬A$ $4- A$ $5- B$ (from 1,4) $→E$ $6- B$ $7- C \land D$ (from 2,6) $→E$ This is ...
6
votes
3answers
70 views

Logic: Can you drop parentheses in a conjunction?

In propositional logic, $p \land (q \land r) = (p \land q) \land r$ , where $p, q$ and $r$ are propositions. Does this mean $p \land (q \land r) = p \land q \land r$ ? If so, why?
0
votes
2answers
30 views

Negating statements with quantifiers in them

First statement, ∀ odd integers n, ∃ an integer k such that n = 2k + 1 Second statement, ∃ m ∈ ℝ such that ∀ n ∈ ℝ, m · n = n Before the negation, I'd like to ask tips on how to translate this ...
1
vote
1answer
6 views

Consequence of compactness lemma

Let $\Gamma=\Sigma \cup \left\lbrace p_i,i\geq 1 \right\rbrace$ a countable set of propositional formulas. Assume also that for every boolean evaluation $u$ that maps every member of $\Sigma$ to true ...
1
vote
2answers
29 views

What is the name of the Boolean function whose output is always one?

For example: f = a.b.c.d + !a.!b.!c.!d + a.!d + !a.b.!c + !b.d + b.c.d + a.b.!c.d + !a.c.!d = 1 ! is logical NOT, . is logiacal AND and + is logical OR. The ...
0
votes
1answer
41 views

Logic : How to determine whether these propositions are contradictory ?

http://postimg.org/image/iips2lwdj/ The question asks to draw a truth table with the values of three propositions (linked), and following this, to "Show that the three propositions are ...
1
vote
1answer
47 views

Prove or disprove a sentence using HPC

according to HPC: Let S be a set of sentences and α that is not in S. Prove or disprove : If $S\cup\{\alpha\} \vdash \beta$ and $S\cup\{\neg \alpha\} \vdash \beta$ then $S\vdash \beta$. It ...
0
votes
4answers
76 views

Use tableau to convert formula to DNF/CNF form

Is there any method that can be used to convert any formula do a DNF/CNF form using only the truth table? For example if I have the following formula p → ¬(q∨r) How can I convert it into DNF? ...
3
votes
2answers
48 views

Write $(p↔q)$ in DNF

I have the following formula: $(p↔q)$ and I have to write in DNF (disjunctive normal form) This is where I got so far: $(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$ but here I got stuck. How ...