Mängdlära: Visa ekvivalens mellan logiska uttryck

Många logiska uttryck kan man uttrycka genom att kombinera ihop boolska variabler med parenteser och operationerna från mängden ${\neg, \land, \lor, \to, \leftrightarrow}$ .

Visa att varje sådant logiskt uttryck är ekvivalent med ett uttryck som kan skrivas ned med endast boolska variabler, parenteser, och symbolerna ur mängden { → , ¬ }.

Du kan ersätta en symbol med en kombination av implikation och negation, om kombinationen och symbolen har samma sanningstabell. Exempel:

$a \land b : \begin{matrix} a & b & a \land b \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}$

Kan du konstruera ett uttryck med endast implikation och/eller negation som har samma sanningstabell?

Smutstvätt skrev:
Du kan ersätta en symbol med en kombination av implikation och negation, om kombinationen och symbolen har samma sanningstabell. Exempel:
$a \land b : \begin{matrix} a & b & a \land b \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}$
Kan du konstruera ett uttryck med endast implikation och/eller negation som har samma sanningstabell?

Gör nu samma sak för de andra symbolerna, så är du i hamn sedan. :)

Smutstvätt skrev:
Gör nu samma sak för de andra symbolerna, så är du i hamn sedan. :)

Hmm, okej.
Jag har lyckats visa två exempel för "och" och "eller" men har fastnat för "ekvivalent"

"Du kan ersätta en symbol med en kombination av implikation och negation, om kombinationen och symbolen har samma sanningstabell."

Vart kan jag läsa om det här? Jag har försökt hitta någon bra källa men lyckas ej.

Har du någon kurslitteratur? Om inte, kan du leta efter böcker om boolsk algebra.

En ekvivalenspil är samma sak som en implikationspil "åt båda hållen". Detta innebär att du kan byta ut $a\leftrightarrow b$ mot $a \to b \land a \leftarrow b$ , vilket är samma sak som $a \to b \land b \to a$ .

En sanningstabell ger nu:

$\begin{matrix} a & b & a \to b & b \to a & a \to b \land b \to a \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}$

Vilket uttryck innehållandes endast negation och implikation är ekvivalent med detta uttryck?

Tips!

Börja gärna med att använda dig av och- samt ellertecken, så blir det lättare. Du kan ersätta dem med dina nyfunna ekvivalenta uttryck efteråt. :)

Jag är en student med samma problem. Uppgiften säger ju att man enbart får använda sig av två symboler. "∧" är väl inte tillåten om man skriver a → b ∧ b → a.

Nej, det stämmer. Det är dock inte svaret, utan endast en omskrivning för att lättare kunna hitta sanningstabellen för ekvivalenspilen. När vi nu hittat sanningstabellen, måste vi hitta ett uttryck med samma sanningstabell, men som endast använder negation och implikation. :)

Svara

Visa senaste svar