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)

-3
votes
0answers
26 views

prove that ¬[P ∨ (L)→M |- M [on hold]

prove that need help to prove that examples
0
votes
1answer
27 views

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

prove [(¬M∧R→Q |- Q∨T really confused :(
-1
votes
1answer
31 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
0answers
50 views

Satisfiability/compactness theorem

I am trying to solve the following problem: Let $\mathcal{F}$ be a set of propositional formulas. Assume that for any valuation map $v$ there is some $F$ $\in$ $\mathcal{F}$ such that $v^*(F) = ...
1
vote
2answers
36 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 ...
6
votes
2answers
87 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
28 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
64 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
28 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
73 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
81 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
177 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
86 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
21 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 ...
2
votes
0answers
26 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
58 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
73 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
22 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
40 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
70 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
38 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
55 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
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
0
votes
1answer
42 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
50 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
58 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
35 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
54 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 ...
1
vote
0answers
23 views

Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
-1
votes
2answers
31 views

Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$

What I would like to do is figure out how to get from $(x \Rightarrow y) $ to $ (y \vee z)$, that what I could AND or OR to $(x \Rightarrow y) $ so as to give $ (y \vee z)$. Breaking this down I ...
1
vote
1answer
16 views

Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...
-3
votes
4answers
78 views

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$ [closed]

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$. I need to prove it by using equivalent sentences.
1
vote
1answer
35 views

Logic normals forms, wolfram, problem.

This is formula which I must write as CNF, DNF and Negation of formula as CNF and DNF: $$(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow \neg r) \rightarrow (p \rightarrow \neg q))$$ ...
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
29 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
28 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
39 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
3answers
62 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
28 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
692 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 ...
12
votes
1answer
177 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
87 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
66 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
48 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
55 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 ...