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
0answers
20 views

Assistance in proving a tautology using a series of logical equivalences.

I am trying to prove, using a series of logical equivalence rules, that the following formula is a tautology: $$[a∧(a→b)∧(b→c)]→c$$ Yet despite numerous successes on other tautologies and logical ...
3
votes
1answer
31 views

Exercise from mathematical Logic about length of sentences in SL

Problem is that : Let $\phi%$ be a sentence of length $n$. Show that for $1\leqslant k<n$, $r(\phi,k)<l(\phi,k) $, where each of them represents the number of left(or right) parenthesis among ...
3
votes
3answers
46 views

Proving $[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R$ is a tautology without using a truth table?

$$[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R\tag{1}$$ How can I prove that $(1)$ is a tautology without using a truth table? I used the identity $$(P\to R)\land(Q\to R)\equiv(P\lor Q)\to R$$ but ...
0
votes
1answer
35 views

tautologies and truth values

I have no idea how to start. really appreciate some help here. Let P and Q be propositions. A statement S (involving P , Q ) is called a tautology iff for any truth-values of P and Q , the statement ...
2
votes
3answers
51 views

Does the => truth table break mathematical induction?

Since $F \Rightarrow F$ and $F \Rightarrow T$ both evaluate to $T$ with the truth table for $\Rightarrow$, does this not break mathematical induction? For example, once you show the base case holds ...
0
votes
2answers
38 views

What's next step to prove this boolean expression?

I need to prove that the first member of this equivalence is true: $$(p\vee q)\wedge (\sim p \wedge (\sim p\wedge q))\equiv \sim p \wedge q$$ I have reached the following point, but I don't know how ...
2
votes
1answer
66 views

Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
0
votes
1answer
43 views

Difference between a proposition and an assertion

It may be a silly doubt, but let me ask this. What is the difference between a proposition and an assertion? I know there's a very thin line between the two terminologies, but I'm unable to get ...
0
votes
1answer
41 views

If $\models \neg \phi$, then $\models \phi^\circ$, where $\phi^\circ$ is the “semi-dual” of $\phi$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, ...
2
votes
1answer
45 views

Proof of derivability

I'm a beginner at mathematical logic and I've come across the following problem: Let $X, Y \subset \mathcal{F}$, where $\mathcal{F}$ is the set of all formulas, and assume that $X \cup \{ \lnot ...
-1
votes
2answers
28 views

Proof using deductive system and modus ponens

The axioms, if p and q are two sentences p$\Rightarrow$(q$\Rightarrow$p) (p$\Rightarrow$(q$\Rightarrow$r))$\Rightarrow$((p$\Rightarrow$q)$\Rightarrow$(p$\Rightarrow$r)) ...
1
vote
2answers
39 views

Is the replacement theorem true for conditionals?

I read about the replacement theorem in Kleene's intro to logic which is as follows: If $\vDash(A\sim B)$ then $\vDash(C_A\sim C_B)$ where $C_A$ is a formula containing formula $A$ and $C_B$ is ...
1
vote
2answers
47 views

Playing with propositional truth-tables

The following is the truth-table describing the definitions which allow us to establish truth values to composite formulae or molecules, which is nothing new: I had an idea about playing with the ...
1
vote
3answers
54 views

Counterexample to “$A \to B, A \to C$, therefore $B \to C$”

We have $A\to B$ and $A\to C$. I need counter-examples to: '$\therefore B\to C$'. More formally, disprove: $$ (A\to B)\land(A\to C)\to (B\to C)$$ I have $A$ is a blackbird, $B$ is 'is black', $C$ ...
-1
votes
1answer
44 views

Proving unsatisfiability with propositional resolution

I'm having trouble understanding how to use the resolution rule to prove if a statement is satisfiable or unsatisfiable. I watched this course lecture on propositional resolution and unsatisfiability ...
1
vote
1answer
39 views

Let $\alpha\in \text{FORM}$. If $\beta \in Sub( \alpha) \implies \beta $ shows up in every formation chain of $\alpha$.

Warning: I'm translating from spanish so probably many terms may sound unfamiliar. Warning 2: I'm probably going to link this question from many others I ask so I don't copy and paste these ...
3
votes
2answers
67 views

Is the following a correct logical proof?

A → (F ∧ P) ~A → (S ∧ R) ~R ∴ P     assume ~P         assume A         F ∧ P ...
4
votes
1answer
48 views

Why is the rule “If x has type σ in the context, we know that x has type σ” needed?

I am trying to get a deeper understanding of why the rules in logic and type theories exist, and am now looking at the simply typed lambda calculus, the typing rules on Wikipedia. The first one is ...
3
votes
1answer
58 views

Proofs as implication and proving implications

I am working through a textbook, on my own, having to do with logic and mathematical proofs, and I have a question about a problem I just completed. Here's the problem: "Suppose $P \to (Q \to ...
0
votes
2answers
36 views

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$ I want to show it algebraically, but I just can't make it work.
1
vote
1answer
62 views

Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...
2
votes
1answer
77 views

Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
0
votes
1answer
31 views

prove [(¬M∧R)∧Q |- Q∨T [closed]

prove [(¬M∧R→Q |- Q∨T really confused :(
-1
votes
1answer
37 views

Solve the following proof : M |- M ∨ {[(Z∨S) ∧ (¬] → (C↔D)}

Solve the following proof : M |- M ∨ {[(Z∨SC↔D)} I try to proof above question with the following (F⋀Z)⋀ → (C↔D) 1 (F⋀Z)→C 2 F⋀Z 1⋀E 3 F 2⋀E really confused :( this ...
1
vote
2answers
40 views

Analyzing logical form of the statements

I have four statements given as exercises in the book: How to prove it. Sa : Alice and Bob are not both in the room. Sb : Alice and Bob are both not in the room. Sc : Either Alice or Bob is not ...
0
votes
1answer
19 views

Propositional Logic - Conditional Proof

I'm confused doing one problem. The problem is to show that $$(P\vee Q \implies R) \implies (P\wedge Q \implies R)$$ using Rule C.P. What I have done so far: Assumed antecedent of the conclusion as ...
6
votes
2answers
91 views

Law of Clavius explained

Law of Clavius states $ \sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
1
vote
1answer
40 views

Universal 2-bit gates

I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
1
vote
3answers
67 views

Omitting parantheses in formulas

Lately I read the following: parentheses can always be omitted, so instead of $((\neg A)\Rightarrow B)$ we may write $(\neg A)\Rightarrow B$. But we may not write $\neg A\Rightarrow B$, because ...
1
vote
2answers
32 views

Solving Boolean expression

(A+C+D)(A+C+D’)(A+C’+D)(A+B’) This is my first attempt on solving four algebraic terms using boolean expression. I am stuck,please help me. I have a test tommorow. Thanks!
4
votes
1answer
78 views

Why do we need truth functional completeness?

This might sound a little too basic, perhaps too basic for most people to talk about. The question seems vaguely structured - I'm not sure how to phrase it better. Question: Why do we need truth ...
0
votes
5answers
86 views

Is it necessary for a statement to have an inverse in propositional logic?

I know that it may be rather self-evident that every statement must possess an inverse, however, is there a way to prove this in propositional calculus or is it considered an axiom? (Note: By the ...
5
votes
1answer
204 views

Formal proof of $(A\lor B)∨C \leftrightarrow A\lor(B\lor C)$

$A\lor B$ by definition $\neg A\implies B$ Deduction rules: $A\implies (B\implies A)$ $(A\implies (B\implies C))\implies ((A\implies B)\implies(A\implies C))$ $(\neg B\implies \neg ...
2
votes
1answer
112 views

$A⇒(B \lor C)$ and $[(A \Rightarrow B) \lor (A \Rightarrow C)]$

[(A⇒ B∨C)] ⇒ [A⇒(¬B⇒C)] ⇒[(A⇒¬B)⇒(A⇒C)] ⇒ [¬(A⇒¬B)∨(A⇒C)]⇒[(A∧B)∨(A⇒C)] [(A⇒B)∨(A⇒C)] is equivalent to A⇒(B∨C). Can I prove [(A∧B)∨(A⇒C)] ⇒ [A⇒(B V C)]? or is there problem in the proof above ...
2
votes
2answers
28 views

is bitwise xor completely distributive?

The bitwise xor operator has the following truth table: $$ \begin{array}{c|cc} \text{^}&0&1\\ \hline 0&0&1\\ 1&1&0 \end{array} $$ It is true that if $a,b,c,d$ are boolean ...
6
votes
1answer
119 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
8
votes
2answers
64 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
1
vote
3answers
86 views

How to prove a logical implication?

Question: Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$ I just don't know how to apply the Rules of ...
2
votes
0answers
24 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
2
votes
1answer
30 views

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$

I'm reviewing discrete math a second time (after it being over a decade since I took the course in college). How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg ...
0
votes
1answer
43 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
0
votes
2answers
126 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
0
votes
2answers
44 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
1
vote
1answer
56 views

How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula ...
0
votes
1answer
44 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
2
votes
1answer
56 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
2answers
61 views

Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s) $$ $$\equiv(\neg p \lor q) ...
2
votes
1answer
36 views

If $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable?

In propositional logic, if $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable? I proved that at least one of $\Sigma \cup \{ ...
2
votes
3answers
57 views

Logical Equivalence

Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. ...
0
votes
1answer
20 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...